_1415. Question 1415.md

1415. Question 1415

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : February 19, 2025

Last updated : February 19, 2025

---

Related Topics : N/A

Acceptance Rate : Unknown

---

V1

My initial attempt which was quite optimal. Achieves $O(n)$ using combinatorics where $n$ is the length of the output string aka the input $n$.

V2

A oneliner I produced with walrus operators. Both in an expanded "bit more readable" version and in the pure oneline state.

---

Solutions

• m1415 v1.py
• m1415 v2 cursed oneliner expanded.py
• m1415 v2 oneliner.py

Python

m1415 v1.py

class Solution:
    # _pm_dfs stands for premature dfs
    def _pm_dfs(self, rem: int, n: int, output: List[str]) -> str :
        if not n :
            return ''.join(output)

        pot_per_path = 2 ** (n - 1)
        (options := ['a', 'b', 'c']).remove(output[-1])

        if rem <= pot_per_path :
            output.append(options[0])
            return self._pm_dfs(rem, n - 1, output)
        output.append(options[1])
        return self._pm_dfs(rem - pot_per_path, n - 1, output)

    def getHappyString(self, n: int, k: int) -> str:
        n -= 1
        pot_n_min_1 = 2 ** n

        match (k - 1) // pot_n_min_1 :
            case 0 :
                return self._pm_dfs(k, n, ['a'])
            case 1 :
                return self._pm_dfs(k - pot_n_min_1, n, ['b'])
            case 2 :
                return self._pm_dfs(k - 2 * pot_n_min_1, n, ['c'])
            case _ :
                return ''

m1415 v2 cursed oneliner expanded.py

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        return (
            _pm_dfs := (
                lambda rem, n, output: 
                    ''.join(output) if not n else 
                    _pm_dfs(
                        rem - (pot_per_path if (indx := int(rem > (pot_per_path := 2 ** (n - 1)))) else 0), 
                        n - 1, 
                        output + ['abc'.replace(output[-1], '')[indx]]
                    )
            )
        )(
            k - x * pot_n_min_1,
            n, 
            [chr(ord('a') + x)]
        ) if (x := (k - 1) // (pot_n_min_1 := 2 ** (n := n - 1))) <= 2 else \
        ''

m1415 v2 oneliner.py

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        return (_pm_dfs := (lambda rem, n, output: ''.join(output) if not n else _pm_dfs(rem - (pot_per_path if (indx := int(rem > (pot_per_path := 2 ** (n - 1)))) else 0), n - 1, output + ['abc'.replace(output[-1], '')[indx]])))(k - x * pot_n_min_1,n, [chr(ord('a') + x)]) if (x := (k - 1) // (pot_n_min_1 := 2 ** (n := n - 1))) <= 2 else ''