"""
# LC 38: Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive
formula: `countAndSay(1) = "1"` and `countAndSay(n)` is the run-length encoding of
`countAndSay(n - 1)`. Return the `n`-th term of the sequence.

## Examples

```text
Input:  n = 1
Output: "1"

Input:  n = 4
Output: "1211"

Input:  n = 5
Output: "111221"
```

## Constraints
- 1 <= n <= 30
"""
from itertools import groupby


class Solution:
    def countAndSay(self, n: int) -> str:
        """
        Approach 1: Iterative simulation O(n * L) where L = avg term length
        Start with "1", build each term by describing the previous one.
        """
        result = "1"
        for _ in range(n - 1):
            # group consecutive identical digits
            result = "".join(str(len(list(g))) + k for k, g in groupby(result))
        return result

    def countAndSay_manual(self, n: int) -> str:
        """
        Approach 2: Same idea without groupby — explicit two-pointer scan
        """
        result = "1"
        for _ in range(n - 1):
            nxt, i = [], 0
            while i < len(result):
                j = i
                while j < len(result) and result[j] == result[i]:
                    j += 1
                nxt.append(str(j - i) + result[i])
                i = j
            result = "".join(nxt)
        return result


# Tests
if __name__ == "__main__":
    sol = Solution()
    # Sequence: 1 -> 11 -> 21 -> 1211 -> 111221
    assert sol.countAndSay(1) == "1"
    assert sol.countAndSay(2) == "11"
    assert sol.countAndSay(3) == "21"
    assert sol.countAndSay(4) == "1211"
    assert sol.countAndSay(5) == "111221"
    assert sol.countAndSay_manual(4) == "1211"
    print("All tests passed")

"""
# LC 730: Count Different Palindromic Subsequences

Given a string `s` that contains only the characters `'a'`, `'b'`, `'c'`, and `'d'`,
return the number of distinct non-empty palindromic subsequences of `s`. Since the
answer may be very large, return it modulo `10^9 + 7`.

## Examples

```text
Input:  s = "bccb"
Output: 6

Input:  s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
Output: 104860361
```

## Constraints
- 1 <= s.length <= 1000
- s consists of only the characters 'a', 'b', 'c', and 'd'
"""


class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        """
        Approach 1: Interval DP O(n^2) time and space
        dp[i][j] = number of distinct palindromic subsequences in s[i..j].

        For each of 4 chars c in {a,b,c,d}:
          lo = first occurrence of c in [i,j]
          hi = last occurrence of c in [i,j]
          - no c in range:       add 0
          - lo == hi (one c):    add 1  ("c")
          - lo+1 == hi (two adj):add 2  ("c", "cc")
          - else:                add dp[lo+1][hi-1] + 2
            (each inner palindrome wrapped by c, plus "c" and "cc")
        """
        MOD = 10**9 + 7
        n = len(s)

        # precompute next[i][c] and prev[i][c] for O(1) lo/hi lookup
        # next_occ[i][c] = next occurrence of char c at or after index i
        # prev_occ[i][c] = prev occurrence of char c at or before index i
        chars = 'abcd'
        next_occ = [[n] * 4 for _ in range(n + 1)]
        prev_occ = [[-1] * 4 for _ in range(n + 1)]

        for i in range(n - 1, -1, -1):
            for ci, c in enumerate(chars):
                next_occ[i][ci] = i if s[i] == c else next_occ[i + 1][ci]

        for i in range(n):
            for ci, c in enumerate(chars):
                prev_occ[i][ci] = i if s[i] == c else prev_occ[i - 1][ci]

        dp = [[0] * n for _ in range(n)]

        # fill by increasing interval length
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                for ci, c in enumerate(chars):
                    lo = next_occ[i][ci]
                    hi = prev_occ[j][ci]
                    if lo > j:          # c not in [i,j]
                        continue
                    elif lo == hi:      # exactly one c
                        dp[i][j] = (dp[i][j] + 1) % MOD
                    elif lo + 1 == hi:  # two adjacent c's
                        dp[i][j] = (dp[i][j] + 2) % MOD
                    else:               # two c's with stuff in between
                        dp[i][j] = (dp[i][j] + dp[lo + 1][hi - 1] + 2) % MOD

        return dp[0][n - 1]


# Tests
if __name__ == "__main__":
    sol = Solution()
    assert sol.countPalindromicSubsequences("bccb") == 6
    # "b","c","c","b","bc","cb","bcb","bccb","cc" — wait, distinct: b,c,bb,cc,bcb,bccb = 6
    assert sol.countPalindromicSubsequences("abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba") == 104860361
    print("All tests passed")

"""
# Count Substrings with Exactly K Distinct Characters

Given a string `s` and an integer `k`, return the count of substrings that contain
exactly `k` distinct characters.

## Examples

```text
Input:  s = "aba", k = 2
Output: 3
Explanation: "ab", "ba", "aba"

Input:  s = "aaa", k = 1
Output: 6
Explanation: all substrings have exactly 1 distinct character
```

## Constraints
- 1 <= s.length <= 10^4
- 1 <= k <= 26
"""
from collections import defaultdict

class Solution:
    def countSubstrings(self, s: str, k: int) -> int:
        # exactly(k) = atMost(k) - atMost(k-1)
        def at_most(k: int) -> int:
            count = left = 0
            freq = defaultdict(int)
            for right, ch in enumerate(s):
                freq[ch] += 1
                # Shrink window until distinct chars <= k
                while len(freq) > k:
                    freq[s[left]] -= 1
                    if freq[s[left]] == 0:
                        del freq[s[left]]
                    left += 1
                # All substrings ending at `right` with left..right are valid
                count += right - left + 1
            return count

        return at_most(k) - at_most(k - 1)


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.countSubstrings("aba", 2) == 3   # "ab","ba","aba"
    assert sol.countSubstrings("aaa", 1) == 6   # all substrings
    assert sol.countSubstrings("abc", 1) == 3   # "a","b","c"
    assert sol.countSubstrings("abc", 2) == 2   # "ab","bc"
    assert sol.countSubstrings("abc", 3) == 1   # "abc"
    print("All tests passed.")

"""
# LC 205: Isomorphic Strings

Given two strings `s` and `t`, determine if they are isomorphic. Two strings are
isomorphic if the characters in `s` can be replaced to get `t` such that all
occurrences of a character map to the same character (bijection — no two characters
may map to the same character).

## Examples

```text
Input:  s = "egg", t = "add"
Output: true

Input:  s = "foo", t = "bar"
Output: false

Input:  s = "paper", t = "title"
Output: true
```

## Constraints
- 1 <= s.length <= 5 * 10^4
- t.length == s.length
- s and t consist of any valid ASCII characters
"""


class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Two maps enforce bijection: s->t and t->s
        s_to_t, t_to_s = {}, {}
        for cs, ct in zip(s, t):
            if s_to_t.get(cs, ct) != ct or t_to_s.get(ct, cs) != cs:
                return False
            s_to_t[cs] = ct
            t_to_s[ct] = cs
        return True


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.isIsomorphic("egg", "add") == True
    assert sol.isIsomorphic("foo", "bar") == False
    assert sol.isIsomorphic("paper", "title") == True
    assert sol.isIsomorphic("badc", "baba") == False
    assert sol.isIsomorphic("a", "a") == True
    print("All tests passed.")

"""
# KMP Pattern Matching (LC 28 variant)

Implement the Knuth-Morris-Pratt (KMP) algorithm for substring search. Given a
`text` and a `pattern`, return the index of the first occurrence of `pattern` in
`text`, or `-1` if not found. The algorithm uses an LPS (Longest Proper Prefix
which is also Suffix) array to achieve O(n + m) time complexity.

## Examples

```text
Input:  text = "hello", pattern = "ll"
Output: 2

Input:  text = "aaaaa", pattern = "bba"
Output: -1

Input:  text = "AABAACAADAABAABA", pattern = "AABA"
Output: 0
```

## Constraints
- 0 <= text.length, pattern.length <= 10^4
- text and pattern consist of lowercase or uppercase English letters
"""
from typing import List


class Solution:
    def computeLPS(self, pattern: str) -> List[int]:
        """
        Build LPS (Longest Proper Prefix which is also Suffix) array O(m).
        LPS[i] = length of longest proper prefix of pattern[0..i] = suffix.
        """
        m = len(pattern)
        lps = [0] * m
        length = 0  # length of previous longest prefix-suffix
        i = 1
        while i < m:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length != 0:
                # don't increment i; try shorter prefix
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
        return lps

    def kmpSearch(self, text: str, pattern: str) -> int:
        """
        Approach 1: KMP O(n+m) — return index of first occurrence, -1 if not found.
        On mismatch at pattern[j], jump to lps[j-1] instead of restarting.
        """
        n, m = len(text), len(pattern)
        if m == 0:
            return 0
        lps = self.computeLPS(pattern)
        i = j = 0  # i = text index, j = pattern index
        while i < n:
            if text[i] == pattern[j]:
                i += 1
                j += 1
            if j == m:
                return i - j  # found at index i-j
            elif i < n and text[i] != pattern[j]:
                if j != 0:
                    j = lps[j - 1]  # key: reuse prefix info
                else:
                    i += 1
        return -1

    def kmpSearchAll(self, text: str, pattern: str) -> List[int]:
        """Return all occurrence indices."""
        n, m = len(text), len(pattern)
        if m == 0:
            return []
        lps = self.computeLPS(pattern)
        results = []
        i = j = 0
        while i < n:
            if text[i] == pattern[j]:
                i += 1
                j += 1
            if j == m:
                results.append(i - j)
                j = lps[j - 1]  # continue searching
            elif i < n and text[i] != pattern[j]:
                j = lps[j - 1] if j != 0 else 0
                if j == 0:
                    i += 1
        return results


# Tests
if __name__ == "__main__":
    sol = Solution()
    assert sol.computeLPS("AABAACAABAA") == [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
    assert sol.kmpSearch("AABAACAADAABAABA", "AABA") == 0
    assert sol.kmpSearch("hello", "ll") == 2
    assert sol.kmpSearch("aaaaa", "bba") == -1
    assert sol.kmpSearchAll("AABAACAADAABAABA", "AABA") == [0, 9, 12]
    print("All tests passed")

"""
# LC 1903: Largest Odd Number in String

Given a string `num` representing a large integer, return the largest-valued odd
integer (as a string) that is a non-empty substring of `num`, or `""` if no odd
integer exists. A substring is a contiguous sequence of characters.

## Examples

```text
Input:  num = "52"
Output: "5"

Input:  num = "4206"
Output: ""

Input:  num = "35427"
Output: "35427"
```

## Constraints
- 1 <= num.length <= 10^5
- num only consists of digits and does not contain any leading zeros
"""


class Solution:
    def largestOddNumber(self, num: str) -> str:
        # Scan from right; first odd digit found → return prefix up to that index
        for i in range(len(num) - 1, -1, -1):
            if int(num[i]) % 2 == 1:
                return num[:i + 1]
        return ""


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.largestOddNumber("52") == "5"
    assert sol.largestOddNumber("4206") == ""
    assert sol.largestOddNumber("35427") == "35427"
    assert sol.largestOddNumber("2") == ""
    assert sol.largestOddNumber("1") == "1"
    print("All tests passed.")

"""
# LC 1392: Longest Happy Prefix

A string is called a *happy prefix* if it is a non-empty prefix which is also a
suffix (excluding the string itself). Given a string `s`, return the longest happy
prefix of `s`, or `""` if no such prefix exists.

## Examples

```text
Input:  s = "level"
Output: "l"

Input:  s = "ababab"
Output: "abab"

Input:  s = "a"
Output: ""
```

## Constraints
- 1 <= s.length <= 10^5
- s contains only lowercase English letters
"""


class Solution:
    def longestPrefix(self, s: str) -> str:
        """
        Approach 1: KMP LPS array O(n)
        LPS[n-1] = length of longest proper prefix of s that is also a suffix.
        That's exactly the happy prefix.
        """
        n = len(s)
        lps = [0] * n
        length, i = 0, 1
        while i < n:
            if s[i] == s[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length != 0:
                length = lps[length - 1]
            else:
                i += 1
        return s[:lps[-1]]

    def longestPrefix_hash(self, s: str) -> str:
        """
        Approach 2: Rolling hash O(n)
        Simultaneously build prefix hash (left→right) and suffix hash (right→left).
        Largest k where prefix_hash[k] == suffix_hash[k] is the answer.
        """
        BASE, MOD = 131, 10**9 + 7
        n = len(s)
        prefix = suffix = 0
        power = 1
        best = 0
        for i in range(n - 1):  # exclude full string (proper prefix/suffix)
            prefix = (prefix * BASE + ord(s[i])) % MOD
            suffix = (ord(s[n - 1 - i]) * power + suffix) % MOD
            power = power * BASE % MOD
            if prefix == suffix:
                best = i + 1
        return s[:best]


# Tests
if __name__ == "__main__":
    sol = Solution()
    assert sol.longestPrefix("level") == "l"
    assert sol.longestPrefix("ababab") == "abab"
    assert sol.longestPrefix("leetcodeleet") == "leet"
    assert sol.longestPrefix("a") == ""
    assert sol.longestPrefix_hash("level") == "l"
    assert sol.longestPrefix_hash("ababab") == "abab"
    print("All tests passed")

"""
# LC 1614: Maximum Nesting Depth of the Parentheses

A valid parentheses string (VPS) has a nesting depth defined as the maximum number
of nested open parentheses. Given a VPS `s`, return the *nesting depth* of `s`.

## Examples

```text
Input:  s = "(1+(2*3)+((8)/4))+1"
Output: 3

Input:  s = "1+(2*3)/(2-1)"
Output: 1
```

## Constraints
- 1 <= s.length <= 100
- s consists of digits, `+`, `-`, `*`, `/`, `(`, and `)` and is a valid VPS
"""


class Solution:
    def maxDepth(self, s: str) -> int:
        depth = max_depth = 0
        for ch in s:
            if ch == '(':
                depth += 1
                max_depth = max(max_depth, depth)
            elif ch == ')':
                depth -= 1
        return max_depth


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.maxDepth("(1+(2*3)+((8)/4))+1") == 3
    assert sol.maxDepth("(1)+((2))+(((3)))") == 3
    assert sol.maxDepth("1+(2*3)/(2-1)") == 1
    assert sol.maxDepth("1") == 0
    assert sol.maxDepth("()") == 1
    print("All tests passed.")

"""
# Minimum Bracket Reversals

Given a bracket string consisting of `'{'` and `'}'`, find the minimum number of
bracket reversals needed to make the string balanced. Return `-1` if it is
impossible (odd-length strings can never be balanced).

## Examples

```text
Input:  s = "}{"
Output: 2

Input:  s = "{{}}"
Output: 0

Input:  s = "{{{"
Output: -1
```

## Constraints
- 1 <= s.length <= 10^5
- s contains only '{' and '}'
"""
from math import ceil


class Solution:
    def countRev(self, s: str) -> int:
        """
        Approach 1: Stack-based O(n) time, O(n) space
        Remove matched {} pairs; remaining is }}}...{{{
        Answer: ceil(close/2) + ceil(open/2)
        """
        if len(s) % 2 != 0:
            return -1  # odd length can never be balanced

        stack = []
        for ch in s:
            if ch == '{':
                stack.append(ch)
            else:  # ch == '}'
                if stack and stack[-1] == '{':
                    stack.pop()  # matched pair, cancel out
                else:
                    stack.append(ch)

        # remaining stack is all }'s followed by all {'s
        close = sum(1 for c in stack if c == '}')
        open_ = sum(1 for c in stack if c == '{')
        return ceil(close / 2) + ceil(open_ / 2)


# Tests
if __name__ == "__main__":
    sol = Solution()
    assert sol.countRev("}{") == 2       # }{ -> {{ (1 rev) -> {} (1 rev)
    assert sol.countRev("{{}}") == 0     # already balanced
    assert sol.countRev("{{{") == -1     # odd length
    assert sol.countRev("}}{{") == 2     # }}{{ -> 2 reversals
    assert sol.countRev("}{{}}{") == 2
    print("All tests passed")

"""
# Rabin-Karp Rolling Hash (LC 28 variant)

Implement the Rabin-Karp algorithm for substring search using a rolling hash.
Given strings `haystack` and `needle`, return the index of the first occurrence of
`needle` in `haystack`, or `-1` if not found.

## Examples

```text
Input:  haystack = "hello", needle = "ll"
Output: 2

Input:  haystack = "aaaaa", needle = "bba"
Output: -1

Input:  haystack = "mississippi", needle = "issip"
Output: 4
```

## Constraints
- 0 <= haystack.length, needle.length <= 5 * 10^4
- haystack and needle consist of only lowercase English letters
"""


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        """
        Approach 1: Rabin-Karp rolling hash O(n+m) average, O(nm) worst case
        Hash needle; slide window over haystack updating hash in O(1).
        Verify on hash match to handle collisions.
        """
        n, m = len(haystack), len(needle)
        if m == 0:
            return 0
        if m > n:
            return -1

        BASE, MOD = 31, 10**9 + 7
        # precompute BASE^(m-1) mod MOD
        power = pow(BASE, m - 1, MOD)

        def char_val(c: str) -> int:
            return ord(c) - ord('a') + 1

        # compute hash of needle and first window
        needle_hash = 0
        window_hash = 0
        for i in range(m):
            needle_hash = (needle_hash * BASE + char_val(needle[i])) % MOD
            window_hash = (window_hash * BASE + char_val(haystack[i])) % MOD

        if window_hash == needle_hash and haystack[:m] == needle:
            return 0

        for i in range(1, n - m + 1):
            # roll: remove leftmost char, add new rightmost char
            window_hash = (window_hash - char_val(haystack[i - 1]) * power) % MOD
            window_hash = (window_hash * BASE + char_val(haystack[i + m - 1])) % MOD
            if window_hash == needle_hash and haystack[i:i + m] == needle:
                return i

        return -1

    def strStr_naive(self, haystack: str, needle: str) -> int:
        """Approach 2: Brute force O(nm) — baseline for comparison"""
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            if haystack[i:i + m] == needle:
                return i
        return -1


# Tests
if __name__ == "__main__":
    sol = Solution()
    assert sol.strStr("hello", "ll") == 2
    assert sol.strStr("aaaaa", "bba") == -1
    assert sol.strStr("", "") == 0
    assert sol.strStr("mississippi", "issip") == 4
    assert sol.strStr_naive("hello", "ll") == 2
    print("All tests passed")

"""
# LC 1021: Remove Outermost Parentheses

A valid parentheses string (VPS) can be decomposed into primitive parts — VPS
substrings that cannot be split further. Remove the outermost parentheses of every
primitive string in the primitive decomposition of `s`.

## Examples

```text
Input:  s = "(()())(())"
Output: "()()()"

Input:  s = "(()())(())(()(()))"
Output: "()()()()(())"

Input:  s = "()()"
Output: ""
```

## Constraints
- 1 <= s.length <= 10^5
- s is a valid parentheses string
"""


class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        # Track depth; skip char when transitioning 0->1 (open) or 1->0 (close)
        result = []
        depth = 0
        for ch in s:
            if ch == '(':
                if depth > 0:          # not the outermost open
                    result.append(ch)
                depth += 1
            else:
                depth -= 1
                if depth > 0:          # not the outermost close
                    result.append(ch)
        return ''.join(result)


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.removeOuterParentheses("(()())(())") == "()()()"
    assert sol.removeOuterParentheses("(()())(())(()(()))") == "()()()()(())"
    assert sol.removeOuterParentheses("()()") == ""
    assert sol.removeOuterParentheses("((()))") == "(())"
    print("All tests passed.")

"""
# LC 151: Reverse Words in a String

Given a string `s`, reverse the order of the words. A word is defined as a sequence
of non-space characters. Multiple spaces between words are collapsed to a single
space, and leading/trailing spaces are removed.

## Examples

```text
Input:  s = "  hello world  "
Output: "world hello"

Input:  s = "a good   example"
Output: "example good a"
```

## Constraints
- 1 <= s.length <= 10^4
- s contains English letters, digits, and spaces
- There is at least one word in s
"""


class Solution:
    # Approach 1: split + reverse — O(n) time, O(n) space
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split()[::-1])

    # Approach 2: manual reverse (O(1) extra space conceptually)
    # Reverse entire string, then reverse each word in-place.
    def reverseWords_inplace(self, s: str) -> str:
        chars = list(s.strip())
        # Step 1: reverse whole array
        chars.reverse()
        # Step 2: reverse each individual word
        start = 0
        for i in range(len(chars) + 1):
            if i == len(chars) or chars[i] == ' ':
                chars[start:i] = chars[start:i][::-1]
                start = i + 1
        # Collapse multiple spaces
        return ' '.join(''.join(chars).split())


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.reverseWords("  hello world  ") == "world hello"
    assert sol.reverseWords("a good   example") == "example good a"
    assert sol.reverseWords("  Bob    Loves  Alice   ") == "Alice Loves Bob"
    assert sol.reverseWords_inplace("  hello world  ") == "world hello"
    print("All tests passed.")

"""
# LC 796: Rotate String

Given two strings `s` and `goal`, return `true` if and only if `s` can become
`goal` after some number of *shifts* (rotating left by one position moves the first
character to the end).

## Examples

```text
Input:  s = "abcde", goal = "cdeab"
Output: true

Input:  s = "abcde", goal = "abced"
Output: false
```

## Constraints
- 1 <= s.length <= 100
- s.length == goal.length
- s and goal consist of lowercase English letters
"""


class Solution:
    # Approach 1: try all rotations — O(n^2)
    def rotateString_brute(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        for i in range(len(s)):
            if s[i:] + s[:i] == goal:
                return True
        return False

    # Approach 2: s+s contains every rotation — O(n) with KMP/built-in
    def rotateString(self, s: str, goal: str) -> bool:
        return len(s) == len(goal) and goal in s + s


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.rotateString("abcde", "cdeab") == True
    assert sol.rotateString("abcde", "abced") == False
    assert sol.rotateString("", "") == True
    assert sol.rotateString("a", "a") == True
    assert sol.rotateString("aa", "a") == False
    assert sol.rotateString_brute("abcde", "cdeab") == True
    print("All tests passed.")

"""
# LC 214: Shortest Palindrome

Given a string `s`, you can add characters in front of it. Return the shortest
palindrome you can form by performing this operation.

## Examples

```text
Input:  s = "aacecaaa"
Output: "aaacecaaa"

Input:  s = "abcd"
Output: "dcbabcd"
```

## Constraints
- 0 <= s.length <= 5 * 10^4
- s consists of lowercase English letters only
"""


class Solution:
    def shortestPalindrome(self, s: str) -> str:
        """
        Approach 1: KMP on s + '#' + reverse(s) O(n) time and space
        The LPS value at the last position = length of longest palindromic prefix.
        Prepend reverse of the remaining suffix to make the whole string a palindrome.
        '#' separator prevents LPS from crossing the boundary.
        """
        if not s:
            return s
        rev = s[::-1]
        t = s + '#' + rev
        # compute LPS for t
        lps = [0] * len(t)
        length, i = 0, 1
        while i < len(t):
            if t[i] == t[length]:
                length += 1
                lps[i] = length
                i += 1
            elif length != 0:
                length = lps[length - 1]
            else:
                i += 1
        # lps[-1] = length of longest palindromic prefix of s
        pal_prefix_len = lps[-1]
        return rev[:len(s) - pal_prefix_len] + s

    def shortestPalindrome_hash(self, s: str) -> str:
        """
        Approach 2: Rolling hash O(n) — find largest k where s[:k] is palindrome.
        Forward hash == backward hash means s[:k] is a palindrome.
        """
        BASE, MOD = 131, 10**9 + 7
        fwd = bwd = 0
        power = 1
        best = 0
        for i, c in enumerate(s):
            v = ord(c)
            fwd = (fwd * BASE + v) % MOD
            bwd = (bwd + v * power) % MOD
            power = power * BASE % MOD
            if fwd == bwd:
                best = i + 1  # s[:best] is a palindrome (probabilistic)
        return s[best:][::-1] + s


# Tests
if __name__ == "__main__":
    sol = Solution()
    assert sol.shortestPalindrome("aacecaaa") == "aaacecaaa"
    assert sol.shortestPalindrome("abcd") == "dcbabcd"
    assert sol.shortestPalindrome("") == ""
    assert sol.shortestPalindrome("a") == "a"
    assert sol.shortestPalindrome_hash("aacecaaa") == "aaacecaaa"
    assert sol.shortestPalindrome_hash("abcd") == "dcbabcd"
    print("All tests passed")

"""
# LC 451: Sort Characters By Frequency

Given a string `s`, sort it in decreasing order based on the frequency of
characters. If two characters have the same frequency, either order is acceptable.
Return the sorted string.

## Examples

```text
Input:  s = "tree"
Output: "eert"

Input:  s = "cccaaa"
Output: "cccaaa"

Input:  s = "Aabb"
Output: "bbAa"
```

## Constraints
- 1 <= s.length <= 5 * 10^5
- s consists of uppercase and lowercase English letters and digits
"""
from collections import Counter

class Solution:
    # Approach 1: Counter + sort — O(n log n)
    def frequencySort(self, s: str) -> str:
        freq = Counter(s)
        # Sort characters by frequency descending, then build result
        return ''.join(ch * cnt for ch, cnt in freq.most_common())

    # Approach 2: Bucket sort — O(n)
    def frequencySort_bucket(self, s: str) -> str:
        freq = Counter(s)
        # Buckets indexed by frequency (max freq = len(s))
        buckets = [''] * (len(s) + 1)
        for ch, cnt in freq.items():
            buckets[cnt] += ch * cnt
        return ''.join(reversed(buckets))


# Tests
if __name__ == '__main__':
    sol = Solution()
    # Multiple valid outputs; check sorted freq property
    res = sol.frequencySort("tree")
    assert res[0] == res[1] == 'e' and set(res) == {'e', 'r', 't'}
    assert sol.frequencySort("cccaaa") in ("cccaaa", "aaaccc")
    assert sol.frequencySort("Aabb") in ("bbAa", "bbaA")
    res2 = sol.frequencySort_bucket("tree")
    assert res2[0] == res2[1] == 'e'
    print("All tests passed.")

"""
# LC 8: String to Integer (atoi)

Implement `myAtoi(string s)` which converts a string to a 32-bit signed integer.
The algorithm: (1) skip leading whitespace, (2) read optional `+`/`-` sign,
(3) read digits until a non-digit character, (4) clamp result to `[-2^31, 2^31-1]`.

## Examples

```text
Input:  s = "42"
Output: 42

Input:  s = "   -42"
Output: -42

Input:  s = "4193 with words"
Output: 4193

Input:  s = "-91283472332"
Output: -2147483648
```

## Constraints
- 0 <= s.length <= 200
- s consists of English letters, digits, `' '`, `'+'`, `'-'`, and `'.'`
"""


class Solution:
    def myAtoi(self, s: str) -> int:
        INT_MIN, INT_MAX = -(2**31), 2**31 - 1
        i, n = 0, len(s)

        # Step 1: skip leading whitespace
        while i < n and s[i] == ' ':
            i += 1

        # Step 2: read optional sign
        sign = 1
        if i < n and s[i] in '+-':
            sign = -1 if s[i] == '-' else 1
            i += 1

        # Step 3: read digits, stop at first non-digit
        result = 0
        while i < n and s[i].isdigit():
            result = result * 10 + int(s[i])
            i += 1

        # Step 4: apply sign and clamp to 32-bit signed integer range
        result *= sign
        return max(INT_MIN, min(INT_MAX, result))


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.myAtoi("42") == 42
    assert sol.myAtoi("   -42") == -42
    assert sol.myAtoi("4193 with words") == 4193
    assert sol.myAtoi("words and 987") == 0
    assert sol.myAtoi("-91283472332") == -(2**31)
    assert sol.myAtoi("91283472332") == 2**31 - 1
    assert sol.myAtoi("  +0 123") == 0
    print("All tests passed.")

"""
# LC 1781: Sum of Beauty of All Substrings

The *beauty* of a string is the difference between the maximum frequency and the
minimum frequency of any character in it. Return the sum of beauty of all substrings
of `s`.

## Examples

```text
Input:  s = "aabcb"
Output: 5

Input:  s = "aabcbaa"
Output: 17
```

## Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters only
"""


class Solution:
    def beautySum(self, s: str) -> int:
        total = 0
        for i in range(len(s)):
            freq = [0] * 26
            for j in range(i, len(s)):
                freq[ord(s[j]) - ord('a')] += 1
                # Compute beauty in O(26): max_freq - min_freq (ignore zeros)
                active = [f for f in freq if f > 0]
                total += max(active) - min(active)
        return total


# Tests
if __name__ == '__main__':
    sol = Solution()
    assert sol.beautySum("aabcb") == 5
    assert sol.beautySum("aabcbaa") == 17
    assert sol.beautySum("a") == 0
    assert sol.beautySum("aa") == 0
    print("All tests passed.")

"""
# Z-Function Pattern Matching

Compute the Z-array for string `s`, where `Z[i]` is the length of the longest
substring starting at `s[i]` that matches a prefix of `s`. Used for O(n + m)
pattern matching by building `pattern + '#' + text` and checking where `Z[i] == m`.

## Examples

```text
Input:  s = "aabxaa"
Output: Z = [0, 1, 0, 0, 2, 1]

Input:  text = "AABAACAADAABAABA", pattern = "AABA"
Output: match indices = [0, 9, 12]
```

## Constraints
- 0 <= s.length <= 10^5
- s consists of uppercase or lowercase English letters
"""
from typing import List


class Solution:
    def zFunction(self, s: str) -> List[int]:
        """
        Approach 1: Z-array O(n) time and space
        Z[i] = length of longest substring starting at i matching prefix of s.
        Maintain [l, r] = rightmost Z-box seen so far.
        """
        n = len(s)
        z = [0] * n
        l, r = 0, 0
        for i in range(1, n):
            if i < r:
                # reuse: Z[i] >= min(Z[i-l], r-i), then try to extend
                z[i] = min(z[i - l], r - i)
            # extend as far as possible
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1
            # update rightmost Z-box
            if i + z[i] > r:
                l, r = i, i + z[i]
        return z

    def patternSearch(self, text: str, pattern: str) -> List[int]:
        """
        Use Z-function for pattern matching: build pattern + '#' + text
        Positions where Z[i] == len(pattern) are match starts.
        """
        m = len(pattern)
        combined = pattern + '#' + text
        z = self.zFunction(combined)
        return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]


# Tests
if __name__ == "__main__":
    sol = Solution()
    # z[0] is conventionally 0 (or n, but we use 0)
    assert sol.zFunction("aabxaa") == [0, 1, 0, 0, 2, 1]
    assert sol.zFunction("aaaa") == [0, 3, 2, 1]
    assert sol.zFunction("abcabc") == [0, 0, 0, 3, 0, 0]

    assert sol.patternSearch("aabxaa", "aa") == [0, 4]
    assert sol.patternSearch("AABAACAADAABAABA", "AABA") == [0, 9, 12]
    print("All tests passed")