def max_consecutive_ones(nums: list[int]) -> int:

        # Aux state: track current streak
        count = 0

        # Aux state: track max streak
        max_count = 0

        # Left Pointer: iterate array
        for right in range(len(nums)):
            
            # Condition: while consecutive 1's is true
            if nums[right] == 1:
                # Aux state: add to streak
                count += 1
                max_count = max(max_count, count)
            else:
                # Aux state: reset streak
                count = 0

        return max_count

    # max_consecutive_ones([1,1,0,1,1,1]) -> 3

    def is_palindrome(s: str) -> bool:

        # Left: start of array
        # Right: end of array
        left, right = 0, len(s) - 1

        # Break when left and right pointers match 
        # when the middle of the array is hit
        while left < right:

            # if palindrome invariant is broken
            if s[left] != s[right]:
                return False

            # shrink left and right pointers towards middle
            left += 1
            right -= 1

        # valid palindrome
        return True

    # is_palindrome("radar") -> True
    # is_palindrome("hello") -> False

    def longest_unique_substring(s: str) -> int:

        # Left: start of window
        left = 0

        # Window data: stores unique chars within window range
        char_set = set()

        # Window data: stores max window found up to now
        maxLength = 0

        # Right: end of window, expand window range as we iterate
        for right in range(len(s)):

            # Invariant: window holds list of unique chars
            # Broken: if condition is broken, shrink window from the 
            # left side until the unique char condition is true again
            while s[right] in char_set:

                # Window data: remove char on left boundary of window
                char_set.remove(s[left])
                
                # Left: start of window, shrink window range
                left += 1
            
            # Invariant: window holds list of unique chars

            # Window data: add char unique list, guaranteed to be unique
            char_set.add(s[right])
  
            # Window data: check global max
            maxLength = max(maxLength, right - left + 1)

        return maxLength

    # longest_unique_substring("abcabcbb") -> 3

    # linked list node definition
    class ListNode:
        def __init__(self, value=0, next=None):
            self.value = value
            self.next = next

    def has_cycle(head: ListNode) -> bool:
        
        # Tortoise, hare pointers: same starting index
        slow, fast = head, head

        while fast and fast.next:

            # Tortoise pointer: x1 steps
            # Hare pointer: x2 steps
            slow = slow.next
            fast = fast.next.next

            # if pointers match, cycle exists
            # will be hit a n/2 iterations
            if slow == fast:
                return True

        # reached end of list, no cycles
        return False

    # LinkedList: 1 -> 2 -> 3 -> 4 -> 2
    # has_cycle(head) -> True

    def partition(nums, pivot):

        # Left: partition flip slot
        left = 0

        # Right: iterate array checking condition
        for right in range(len(nums)):

            # Condition: if curr element value is less than pivot val, 
            # flip element to left side of array in place
            if nums[right] < pivot:

                # Flip: swap element with flip slot
                nums[left], nums[right] = nums[right], nums[left]

                # Left: iterate flip slot by 1 step
                left += 1

        # Left: ends up pointing to first index where all elements 
        # are greater than the pivot value
        return (nums, left)

    # partition([9, 3, 5, 2, 8, 1, 6], 5) -> ([3, 2, 1, 5, 8, 9, 6], 5)

    def merge_sorted_arrays(arr1, arr2):

        result = []

        # i / j: 2 pointers
        i, j = 0, 0

        # i / j: parallel iterate array, while elements remain in both lists 
        while i < len(arr1) and j < len(arr2):

            # Merge: append smaller element between arrays 
            if arr1[i] < arr2[j]:
                result.append(arr1[i])
                i += 1
            else:
                result.append(arr2[j])
                j += 1
        
        # Merge: one list has run out of elements, 
        # append list with remaining elements as its already sorted
        result.extend(arr1[i:])
        result.extend(arr2[j:])

        # merged sorted array
        return result

    # merge_sorted_arrays([1, 3, 5], [2, 4, 6]) -> [1, 2, 3, 4, 5, 6]

    def split_words(s: str, delim: str = ' ') -> list[str]:

        words = []

        # Left: frozen until right hits delim
        left = 0

        # Right: iterate list checking for delim
        right = 0

        # Right: iterate list
        while right < len(s):

            # Right condition: delimiter found
            if s[right] == delim:

                # Logic: check if non-empty word, 
                # then splice word and add to array
                if left != right:
                    words.append(s[left:right])

                # Left: Catch up, move to right+1, to 1 index
                # after the delimiter, to restart scanning for delim
                left = right + 1

            # Right: iterate pointer, either after delim
            # or to next index
            right += 1

        # Right: hit end of string, check if last word exists
        if left < len(s):
            words.append(s[left:])

        return words


    # split_words("catch up pointers example") -> ['catch', 'up', 'pointers', 'example']

    def threeSum(nums):

        result = []
        nums.sort()

        # k: 3 pointers, i, left, right

        # i: iterate pointer as 'frozen' pointer
        for i in range(len(nums)):

            # i: Avoid duplicates
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Inner two pointer approach:

            # Left: 1 index after frozen pointer
            # Right: right end of array
            left, right = i + 1, len(nums) - 1
            while left < right:

                # Condition: check if triplet sum == 0
                current_sum = nums[i] + nums[left] + nums[right]                
                if current_sum == 0:

                    # Match: add triplet
                    result.append([nums[i], nums[left], nums[right]])

                    # Left / Right: Iterate to avoid duplicates
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                # Search: 
                # left end has lowest numbers, right end has highest numbers,
                # shift towards whichever gets triplet sum closer to 0

                # Left: shift towards higher numbers
                elif current_sum < 0:
                    left += 1 

                # Right: shift towards lower numbers 
                else:
                    right -= 1

        return result

    # threeSum([-1, 0, 1, 2, -1, -4]) -> [[-1, -1, 2], [-1, 0, 1]]

    def longestPalindrome(s: str) -> str:

        # Preprocess the string to handle even length palindromes
        t = "#".join(f"^{s}$")
        n = len(t)
        p = [0] * n
        center = right = 0

        
        for i in range(1, n - 1):

            # Mirror of `i` with respect to `center`
            mirror = 2 * center - i

            # If within bounds of the current right boundary, use mirror head start 
            if i < right:
                p[i] = min(right - i, p[mirror])

            # Expand around 'i' while palindrome condition true
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # Update the center and right boundary if the palindrome is expanded
            if i + p[i] > right:
                center = i
                right = i + p[i]

        # Find the maximum length palindrome
        maxLen, centerIndex = max((n, i) for i, n in enumerate(p))

        # Convert index back to original string
        start = (centerIndex - maxLen) // 2
        
        # Grab palindrome substring
        return s[start: start + maxLen]

if __name__ == "__main__":

    sol = Solution()

    testCases = [

        # Regular strings
        "hello",
        "aaa",
        "abc",

        # Edge cases
        "",
        "a",

        # Palindrome patterns
        "racecar",
        "abba",
        "abca",
    ]

    for s in testCases:

        chars = list(s)
        sol.reverseString(chars)

        # !r calls repr() on the value before inserting it into the f-string,
        # for strings that means it wraps the output in quotes
        # w/ : 'hello' -> 'olleh'
        # w/o: hello -> hello
        print(f"{s!r} -> {''.join(chars)!r}")

    def reverseString(self, s: List[str]) -> None:
        
        # Two Pointer Approach (In-Place)
        
        # Substring Representation:
        #   - Maintain window [left, right] representing characters to swap
        #   - Goal: Swap characters until window meets in the middle
        
        # Idea:
        #   - Initialize two pointers at the ends of the array
        #   - Swap s[left] and s[right]
        #   - Move pointers inward
        #   - Stop when left >= right

        # Yes, this is a dumb way to do recursion, just a test for syntax

        def helper(left, right):
            if left >= right:
                return
            
            # Swap characters at the current ends
            s[left], s[right] = s[right], s[left]
            
            # Recurse inward
            helper(left + 1, right - 1)
        
        helper(0, len(s) - 1)

        # overall: tc O(n)
        # overall: sc O(n)

    def reverseString(self, s: List[str]) -> None:
        
        # Two Pointer Approach (In-Place)
        
        # Substring Representation:
        #   - Maintain window [left, right] representing characters to swap
        #   - Goal: Swap characters until window meets in the middle
        
        # Idea:
        #   - Initialize two pointers at the ends of the array
        #   - Swap s[left] and s[right]
        #   - Move pointers inward
        #   - Stop when left >= right

        left = 0
        right = len(s) - 1

        # tc: iterate over half the array O(n)
        while left < right:

            # Swap characters at left and right
            s[left], s[right] = s[right], s[left]

            # Shrink window from both ends
            left += 1
            right -= 1
         
        # overall: tc O(n)
        # overall: sc O(1)

if __name__ == "__main__":
    sol = Solution()

    categories = {
        "palindrome": ["racecar", "abcba", "aaaaaaaa"],
        "not palindrome": ["ksjdnfjgnsdkf", "ab"]
    }

    for (category, tests) in categories.items():

        for case in tests:

            res = sol.isPalindrome(case)

            print(f"{'category':<10} -> {category}")
            print(f"{'case':<10} -> {case}")
            print(f"{'result':<10} -> {res}")
            print("\n--------------------------\n")

    def isPalindrome(self, s: str) -> bool:
        
        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

        # Helper: to skip over non alphaNum chars
        def isAlphaNum(c):
            if (ord('a') <= ord(c) <= ord('z') or
                ord('A') <= ord(c) <= ord('Z') or
                ord('0') <= ord(c) <= ord('9')):
                return True
            return False

        # Helper: to turn uppercase into lowercase
        def upperClean(c):
            if (ord('A') <= ord(c) <= ord('Z')):
                return chr(ord(c)+32)
            return c

        # sc: cleaned version of string O(n)
        cleaned = []

        # tc: iterate string O(n)
        for c in s:

            # only grab alphaNum chars
            if isAlphaNum(c):
                cleaned.append(upperClean(c))
        
        # tc: join alphaNum list O(n)
        phrase = "".join(cleaned)

        # Note:
        # Slicing: [start:stop:step]
        # if start and stop are omitted, slice includes the entire sequence
        # if step is -1, indicates to traverse in reverse

        # tc: single iteration over the two strings
        # sc: creates new reversed string
        res = phrase == phrase[::-1]

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def isPalindrome(self, s: str) -> bool:
        
        # Helper: to skip over non alphaNum chars
        def isAlphaNum(c):
            if (ord('a') <= ord(c) <= ord('z') or
                ord('A') <= ord(c) <= ord('Z') or
                ord('0') <= ord(c) <= ord('9')):
                return True
            return False

        # Helper: to turn uppercase into lowercase
        def UpperClean(c):
            if (ord('A') <= ord(c) <= ord('Z')):
                return chr(ord(c)+32)
            return c

        # outer ends pointers
        # sc: O(1)
        left = 0
        right = len(s)-1

        # tc: O(1)
        while left < right:

            # skip non-alphaNum, while within bounds
            # tc: O(n)
            while left < right and not isAlphaNum(s[left]):
                left += 1

            # tc: O(n)
            while left < right and not isAlphaNum(s[right]):
                right -= 1

            # grab pointer values
            # sc: O(1)
            leftChar = s[left]
            rightChar = s[right]

            # Convert to lowercase
            leftClean = UpperClean(leftChar)
            rightClean = UpperClean(rightChar)

            # Check: if chars match
            # tc: O(1)
            if leftClean != rightClean:
                return False

            # Shrink pointers towards center
            # tc: O(1)
            left += 1
            right -= 1

        # overall: tc O(n)
        # overall: tc O(1)
        return True

if __name__ == "__main__":

    sol = Solution()

    sections = {
        "palindromes":        ["racecar", "aaa", "a", ""],
        "one deletion":       ["abca", "baabx", "deeee", "raceecar"],
        "near palindrome":    ["abba", "abbba"],
        "non palindromes":    ["abc", "abcdef", "leetcode"],
        "boundary patterns":  ["ab", "ac", "ba", "aaab"],
    }

    testCases = []

    # for each section
    for (label, cases) in sections.items():
        
        # for each testcase in that section
        for s in cases:
        
            # add to our test list
            testCases.append((label, s))

    # print
    for (label, s) in testCases:

        # No shallow copy needed:
        # strings are immutable in Python, validPalindrome cannot mutate s
        res = sol.validPalindrome(s)

        print(f"{'case':<18} -> {label}")
        print(f"{'input':<18} -> {s!r}")
        print(f"{'isPalindrome':<18} -> {res}")
        print("\n------------------------\n")

    def validPalindrome(self, s: str) -> bool:
        
        # Two Pointers (Opposite Ends) Greedy Decision at First Mismatch

        # Substring Representation:
        #   - Maintain window [left, right] over string s
        #   - Move inward while characters match
        #   - On first mismatch, we are allowed to delete at most ONE character
        
        # Greedy Insight:
        #   - If s[left] != s[right], only two deletions can fix the mismatch:
        #         1) Delete s[left]
        #         2) Delete s[right]
        #   - Deleting any other character will NOT fix this mismatch.
        #   - Therefore, trying these two options is sufficient and exhaustive.
        #   - This makes the solution greedy: we resolve the first conflict locally
        #     and never revisit earlier decisions.

        # Helper: check if strings are palindromes
        def isPalindrome(i: int, j: int) -> bool:

            # tc: worst case O(n)
            while i < j:

                # If char fails palindrome check
                if s[i] != s[j]:
                    return False

                # shrink towards center
                i += 1
                j -= 1

            return True

        # original string length
        n = len(s)


        def isPalindromeSafety(s2):

            # Opposite Ends Variables
            # sc: O(1)
            left = 0
            right = n - 1

            # tc: iterate over n O(n)
            while left < right:

                # Safety hit:
                # current mismatch chars fails palindrome check,
                # check if passes by skipping mismatch chars
                if s[left] != s[right]:

                    # Greedy Skip:
                    # Create two candidate substrings, 
                    # each by skipping one of the 2 mismatched characters
                    return isPalindrome(left + 1, right) or isPalindrome(left, right - 1)

                left += 1
                right -= 1

            return True

        # overall: tc O(n)
        # overall: sc O(1)
        return isPalindromeSafety(s)

    def validPalindrome(self, s: str) -> bool:
        
        # Two Pointers + Slicing

        # Substring Representation:
        #   - Opposite ends over  [left, right] over string s
        #   - On first mismatch, try removing and continue:
        #         1) left character
        #         2) right character
        #   - if failure, false
        #   - Use simple reverse [::-1] slicing to verify palindrome

        n = len(s)

        # Opposite Ends Variables
        # sc: O(n) due to slicing creating new substrings
        left = 0
        right = n - 1


        # Helper:
        # su using slicing
        def isPalindrome(sub: str) -> bool:

            # CPython Interpreter:
            #
            #   Slicing: [::-1] is implemented at the interpreter level in CPython
            #   Copy:    sub[::-1] creates a reversed string copy using fast C memory operations
            #   Equal:   sub == sub[::-1] compares strings at C level with fast memory comparison
            #
            # Interpreter level ends up being much faster than a python loop over indices
            #  which adds multiple steps for simple operations
            #
            # tc: O(k), sc: O(k) where k = length of substring
            return sub == sub[::-1]


        # tc: iterate over n O(n)
        while left < right:

            # Safety hit:
            # current mismatch chars fails palindrome check,
            # check if passes by skipping mismatch chars
            if s[left] != s[right]:

                # Greedy Skip:
                # Create two candidate substrings, 
                # each by skipping one of the 2 mismatched characters

                # Slicing:
                # [0:2] = [0, 2) => [0, 1]

                # Skip left char, include right char
                skipLeft = s[left + 1 : right + 1]

                # Include left char, skip right char
                skipRight = s[left : right]         

                # Check if either resulting substring is a palindrome
                return isPalindrome(skipLeft) or isPalindrome(skipRight)

            # Shrink towards center
            left += 1
            right -= 1


        # overall: tc O(n)
        # overall: sc O(n)
        return True

if __name__ == "__main__":

    sol = Solution()

    sections = {
        "same length":  [
                        ("abc", "xyz")],

        "word1 longer": [
                        ("abcd", "xy"), 
                        ("abcde", "x")],

        "word2 longer": [
                        ("ab", "xyzw"), 
                        ("a", "xyzw")],

        "single char":  [
                        ("a", "b")],

        "one empty":    [
                        ("abc", ""), 
                        ("", "xyz")],

        "both empty":   [
                        ("", "")],
    }

    testCases = []

    # for each section
    for label, pairs in sections.items():

        # for each testcase in that section
        for pair in pairs:

            # add to our test list
            testCases.append((label, pair))

    # for each tuple in each section
    for label, (word1, word2) in testCases:

        # No shallow copy needed:
        # strings are immutable in Python,
        # mergeAlternately cannot mutate word1 or word2
        res = sol.mergeAlternately(word1, word2)

        print(f"{'case':<10} -> {label}")
        print(f"{'word1':<10} -> {word1!r}")
        print(f"{'word2':<10} -> {word2!r}")
        print(f"{'merged':<10} -> {res!r}")
        print("\n------------------------\n")

    def mergeAlternately(self, word1: str, word2: str) -> str:
        
        # Two Pointers (Same Direction Traversal)

        # Substring Representation:
        #   - Traverse both strings from left to right
        #   - Append characters alternately from word1 and word2
        #   - If one string finishes first, append the remaining characters
        #
        # Goal:
        #   - Build merged string by alternating characters
        #
        # Pattern:
        #   - Two pointers moving forward independently

        n1 = len(word1)
        n2 = len(word2)

        # Two Pointer Variables
        # sc: O(n1 + n2) for result storage
        i = 0
        j = 0

        # Result list
        # sc: O(n1 + n2)
        merged = []

        # tc: iterate over lists O(min(n1, n2))
        while i < n1 and j < n2:

            # Alternate Appending
            merged.append(word1[i])
            merged.append(word2[j])

            # iterate both lists
            i += 1
            j += 1


        # Word1 has remaining letters
        # tc: O(n1)
        while i < n1:
            merged.append(word1[i])
            i += 1

        # Word2 has remaining letters
        # tc: O(n2)
        while j < n2:
            merged.append(word2[j])
            j += 1

        # Join iterates over list and creates a new string
        # tc: O(n1 + n2)
        # sc: O(n1 + n2)
        res = "".join(merged)

        # overall: tc O(n1 + n2)
        # overall: sc O(n1 + n2)
        return res

    def mergeAlternately(self, word1: str, word2: str) -> str:
        
        # Two Pointers (Same Direction Traversal)

        # Substring Representation:
        #   - Traverse both strings from left to right
        #   - Append characters alternately from word1 and word2
        #   - If one string finishes first, append the remaining characters
        #
        # Goal:
        #   - Build merged string by alternating characters
        #
        # Pattern:
        #   - Two pointers moving forward independently

        n1 = len(word1)
        n2 = len(word2)

        # Two Pointer Variables
        # sc: O(n1 + n2) for result storage
        i = 0
        j = 0

        # Result list
        # sc: O(n1 + n2)
        merged = []

        # tc: iterate over lists O(min(n1, n2))
        while i < n1 and j < n2:

            # Alternate Appending
            merged.append(word1[i])
            merged.append(word2[j])

            i += 1
            j += 1

        #[i::] [start:end:step], 
        # when end:step are omitted, it says "from index i to end"

        # Append remaining characters via slicing
        # Returns "" if index is out of bounds, 
        # so both are always safe to append
        # tc: O(n1 - i) ~= O(n1) or O(n2 - j) ~= O(n2)
        merged.append(word1[i::])
        merged.append(word2[j::])

        # Join iterates over list and creates a new string
        # tc: O(n1 + n2)
        # sc: O(n1 + n2)
        res = "".join(merged)

        # overall: tc O(n1 + n2)
        # overall: sc O(n1 + n2)
        return res

if __name__ == "__main__":
    sol = Solution()

    categories = {
        "equal": (([1,2,3,0,0,0], 3), ([1,2,3], 3)),
        "longer": (([1,2,3,4,5,6,7,0,0], 7), ([4,9],2)),
        "empty": (([0,0,0,0,0,0], 0), ([2,4,5,6,7,8], 6))
    }

    for (category, ((a, ax), (b, bx))) in categories.items():

        cpy = a[:]
        sol.merge(a, ax, b, bx)

        print(f"{'original left':<10} -> {cpy}")
        print(f"{'original right':<10} -> {b}")
        print(f"{'merged':<10} -> {a}")
        print("\n------------------------\n")

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:

        # Two Pointers (Reverse Direction Traversal)

        # Substring Representation:
        #   - nums1 has length m + n
        #   - First m elements are valid
        #   - Last n elements are placeholders (0s)

        # Idea:
        #   - Iterate from right to left across both lists (large num to lower num)
        #     while appending the larger number between the two lists
        #   - Avoid overwriting values in nums1 by going right to left

        # Two Pointer Variables
        # sc: O(1)

        # List1 right most element
        n1 = m - 1

        # List2 right most element
        n2 = n - 1

        # Next write index for newest largest element in nums1
        write = m + n - 1

        # Exit: when either array is exhausted
        # tc: iterate over nums1 and nums2 O(m + n)
        while 0 <= n1 and 0 <= n2:

            # Case 2: grab element from list2
            #   - nums2 has the larger value
            if nums1[n1] < nums2[n2]:
                nums1[write] = nums2[n2]

                # Iterate nums2 pointer
                n2 -= 1

            # Case 1: grab element from list1
            #   - nums1 has the larger or equal value
            else:
                nums1[write] = nums1[n1]

                # Iterate nums1 pointer
                n1 -= 1

            # Always iterate write pointer
            write -= 1


        # Exit Catch 1: list1 has elements, list2 exhausted:
        # the remaining list1 elements are already ordered, 
        # nothing to do here


        # Exit Catch 2: list1 exhausted, list2 has elements
        # the remaining list2 elements rae already sorted,
        # simple overwrite into list1 indexes        
        # tc: iterate remaining nums2 elements O(n)
        while 0 <= n2:
            
            # simple overwrite from list2 to list1
            nums1[write] = nums2[n2]
            n2 -= 1
            write -= 1

        # overall: tc O(m + n)
        # overall: sc O(1)

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        
        # Two Pointers (Reverse Direction Traversal)

        # Substring Representation:
        #   - nums1 has length m + n
        #   - First m elements are valid
        #   - Last n elements are placeholders (0s)
        
        # Idea:
        #   - Iterate from right to left across both lists appending the larger number
        #   - We avoid overwriting values in nums1 by going right to left


        # Two Pointer Variables
        # sc: O(1) (in-place modification)

        # Last valid element in nums1
        p1 = m - 1

        # Last element in nums2
        p2 = n - 1

        # Position to write next largest element in num1
        num1Write = m + n - 1

        # Exit: list2 is exhausted
        # tc: iterate through both arrays once O(m + n)
        # sc: in place merge O(1)
        while p2 >= 0:

            # list1 may or may not have elements, list2 has elements

            # Case 1: grab element from list1
            #   - nums1 has elements
            #   - nums1 has larger num
            if p1 >= 0 and nums1[p1] > nums2[p2]:

                # move num1 element 
                nums1[num1Write] = nums1[p1]

                # iterate nums1 pointer
                p1 -= 1

            # Case 2: grab element from list2
            #   - nums2 has no elements
            #   - nums2 has larger num
            else:

                # move num2 element
                nums1[num1Write] = nums2[p2]

                # iterate nums2 pointer
                p2 -= 1

            # iterate write pointer
            num1Write -= 1

        # Exit Catch: list1 may or may not have elements, list2 exhausted
        # nothing to do here,
        # if list1 has elements, they are already ordered, nothing to do
        # if list1 has no elements, then still nothing to do

        # overall: tc O(m + n)
        # overall: sc O(1)

if __name__ == "__main__":

    sol = Solution()

    sections = {
        "no modification":  [
                            [1], 
                            [1,2,3,4]
                            ],

        "general":          [
                            [0,0,1,1,1,2,2,3], 
                            [1,1,2], 
                            [1,2,2,3,3,4], 
                            [1,2,3,4,4,4,4], 
                            [1,1,2,3,3,3,4,5,5]
                            ],

        "all duplicates":   [
                            [2,2,2,2]
                            ],

        "front duplicates": [
                            [5,5,5,5,6,7]
                            ]
    }

    # flatten into (label, nums) tuples
    testCases = []

    # for each section
    for (label, cases) in sections.items():

        # for each testCase in that section
        for testCase in cases:

            # append to our list
            testCases.append((label, testCase))

    for (label, nums) in testCases:

        # Shallow Slice Copy: 
        # grabs list elements before in-place mutation
        # [:] copies the list values, not the reference
        # [start:end] => start defaults to 0, end defaults to len(nums)
        original = nums[:]

        # number of unique values
        k = sol.removeDuplicates(nums)

        # :<10 pads any string to fill width of 10
        print(f"{'Group Type':<10} -> {label}")
        print(f"{'original':<10} -> {original}")
        print(f"{'modified':<10} -> {nums}")

        # nums[:k]: slice to valid unique portion only,
        # elements beyond index k are leftover garbage values
        print(f"{'sliced':<10} -> {nums[:k]}")
        print(f"{'unique k':<10} -> {k}")
        print("\n------------------------\n")

    def removeDuplicates(self, nums: List[int]) -> int:
        
        # Two Pointer Pattern : Read and Write Pointers (Lomuto Quicksort Partition)
        
        # Idea:
        #   - Array is sorted so duplicates will appear consecutively
        #       [1, 1, 1, 1, 2, 2, 2, 3, 4, 5] etc...
        #   - Two Pointers Write/Read
        #       left: holds a left most position for the newest found unique value
        #       fast: scans to find new unique values
        #   - Left End Value: 
        #       Array contains at least 1 duplicate: points to the first duplicate
        #       Array has all unique values: length of the array
    
        n = len(nums) - 1

        # Left most position:
        # Write index for unique values 
        left = 1

        # Right Scanner Pointer:
        # Reads/iterates over array searching for unique value,
        # Sends unique to the write index
        right = 1

        # tc: iterate over n O(n)
        while right <= n:

            # Since array is sorted so duplicates appear consecutively,
            # check previous if match
            if nums[right] != nums[right - 1]:

                # We cannot swap the elements as this would break the 
                # sorted property of the array,
                # thus, we just place the unique element on the write pointer
                nums[left] = nums[right]

                # Iterate write index
                left += 1

            # Iterate scanner
            right += 1

        # left = index of first duplicate value
        # left = number of unique elements (to the left of left)

        # overall: tc O(n)
        # overall: sc O(1)
        return left

if __name__ == "__main__":

    sol = Solution()

    testCases = [

        # Edge cases
        "",
        "a",
        "0",
        "1",

        # Minimal valid cases
        "01",
        "10",

        # Simple repeating groups
        "0011",      # 2
        "000111",    # 3
        "00001111",  # 4

        # Uneven groups
        "00011",     # 2
        "001",       # 1
        "1100",      # 2

        # Alternating pattern
        "010101",    # 5
        "101010",    # 5

        # Long same-character blocks
        "000000",    # 0
        "111111",    # 0

        # Mixed patterns
        "00110011",  # 6
        "1011000",   # 3
        "00110",     # 3

        # Realistic patterns
        "0001110011", # 6
        "100111001",  # 4

        # Random patterns
        "110001110",  # 5
        "010011",     # 3
    ]

    for s in testCases:
        print(s, "=>", sol.countBinarySubstrings(s))

    def countBinarySubstrings(self, s: str) -> int:
        
        # Consecutive Group Lengths Approach (Two Pointers)

        # Idea:
        #   - Track consecutive characters as groups using two pointers.
        #   - prevGroupLength stores length of previous group
        #   - currGroupLength stores current group we scan as we match characters
        #
        #   - The number of groups found, depends on the shorter group:
        
        # Inner Outer Group Calculation:
        #
        #    0000110 =>  ["01", "0011"]
        #      00110 =>  ["01", "0011"]
        #   
        #   We add the min to the total as the length is the number of groups
        #    0001110 => ["01", "0011", "000111"]  
        #   makes 3 individual groups

        n = len(s) - 1

        # Empty Check:
        if n == 0:
            return 0

        # Initialize pointers
        # tc: O(1)

        # Start scanner at index 1, we have labeled index 0 as a group
        right = 1 

        # Start prev group at 0, no group exists before index 0
        prevGroupLen = 0
        
        # Start curr group at 1, we have labeled index 0 as a group
        currGroupLen = 1
        
        # Total number of groups
        res = 0

        # tc: iterate over n O(n)
        while right < n:

            # Extend current group
            if s[right] == s[right-1]:
                currGroupLen += 1

            # Form new group:
            else:
                
                # We add the min to the total as the length is the number of groups
                #   000111 => "01", "0011", "000111"
                res += min(prevGroupLen, currGroupLen)
                
                # Make current group, the new previous group
                prevGroupLen = currGroupLen

                # Start new group length
                currGroupLen = 1


            # Iterate group finder
            right += 1

        # Nothing will trigger the last group to match
        # as no nums will follow the last group
        res += min(prevGroupLen, currGroupLen)

        # overall: tc O(n)
        # overall: sc O(1)
        return res

    def decode(self, encoded: str) -> List[str]:

        # space complexity: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # time complexity: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            right = left
            while encoded[right] != "#":
                right += 1

            # splicing the length of the string
            # BUG: 
            # length is a string, cannot use it to index or add
            # need to use int()
            length = encoded[left:right]

            # skip delimiter, point to start of string
            right += 1

            # splicing the string of 'length' characters
            # time complexity: splice over string n length O(n) for n iterations O(n), leading to O(n^2)
            decoded.append(encoded[right:right + length])

            # skip string, point to start of next len
            left = right + length

        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return decoded

    def decode(self, encoded: str) -> List[str]:
        
        # base 10 strategy 
        # or 2 pointer splice strategy

        decoded = []
        left = 0

        while left < len(encoded):

            # grab length before delim
            currLen = 0
            while encoded[left] != "#":

                # BUG:
                # we need to update currLen, not add to it
                currLen += (10*currLen) + int(encoded[left])
                left += 1
            
            # step past delim
            left += 1
            substring = []

            for _ in range(currLen):
                substring.append(encoded[left])
                left += 1

            decoded.append(''.join(substring))

        return decoded

if __name__ == "__main__":

    sol = Solution()

    testCases = [

        # Edge cases with custom delim
        [],
        [""],
        ["a"],
        ["#"],
        ["##"],

        # Mixed length strings
        ["hello"],
        ["leet", "code"],
        ["abc", "defg", "h"],
        ["racecar", "level", "radar"],
    ]

    # Test encoding + decoding round trip
    for strs in testCases:

        print("Original:", strs)

        encoded = sol.encode(strs)
        decoded = sol.decode(encoded)

        print("Encoded:", encoded)
        print("Decoded:", decoded)
        print("***")

    def encode(self, strs: List[str]) -> str:

        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

        # sc: n strings with m chars O(n * m)
        encoded = []

        # tc: iterate list O(n)
        for s in strs:
            
            # Note:
            # custom delimiter to mark start of string "{length}#" -> "5#""

            # tc: delimiter length proportional to log10(m) ~= O(1)
            encoded.append(str(len(s)) )
            encoded.append("#")
            encoded.append(s)
    
        # overall: tc O(n * m)
        # overall: sc O(n * m)
        return ''.join(encoded)


    def decode(self, encoded: str) -> List[str]:

        # sc: n strings with m chars O(n * m)
        decoded = []
        left = 0

        # tc: iterate over encoded O(n * m)
        while left < len(encoded):

            # set right to start of length prefix
            right = left

            # tc: log 10 (m) ~= O(1)
            # shift right until pointing to delimiter
            while encoded[right] != "#":
                right += 1

            # after:
            # [ 2 # h i ... ]
            #   ^ ^
            #   l r 

            # slice out string length
            length = int(encoded[left:right])

            # skip delimiter, point to start of string
            right += 1

            # after:
            # [ 2 # h i ... ]
            #   ^   ^
            #   l   r 

            # tc: slice out substring of length m 
            decoded.append(encoded[right:right + length])
           
            # set left to start of next custom delimiter
            left = right + length
            
            # after:
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #       ^   ^
            #       r   l

        # overall: tc O(n * m)
        # overall: sc O(n * m)
        return decoded

    def encode(self, strs: List[str]) -> str:

        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

        # sc: for n strings O(n) store n characters O(n), leading to O(n^2)
        encoded = []

        # tc: iterate over list of strings n length O(n)
        for s in strs:
            
            # Note:
            # custom delimiter to mark start of string "{length}#" -> "5#""

            # tc: delimiter length proportional to log10(m) ~= O(1)
            encoded.append(str(len(s)) )
            encoded.append("#")
            encoded.append(s)
        
        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return ''.join(encoded)


    def decode(self, encoded: str) -> List[str]:

        # sc: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # tc: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            currLen = 0
            while encoded[left] != "#":

                # grabbing value while calculating base 10 of prev
                currLen = currLen * 10 + int(encoded[left]) 
                left += 1

            # skip delimiter, point to start of string
            left += 1  

            # after:
            # [ 2 # h i ... ]
            #       ^
            #       l  

            # tc: iterate string O(n) for n delimiters O(n), O(n^2)
            substring = []
            for _ in range(currLen):

                # grab string of currLen
                substring.append(encoded[left])
                left += 1
            
            # left is set to start of next length

            # after:
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #           ^
            #           l

            # add string to decoded list of strings
            decoded.append(''.join(substring))


        # overall: tc O(n^2)
        # overall: sc O(n^2)
        return decoded

if __name__ == "__main__":
    sol = Solution()

    categories = {
        "1": ([1,2,3,4,5], 1),
        "2": ([1,2,3,4,5], 2),
        "3": ([1,2,3,4,5], 3),
        "4": ([1,2,3,4,5], 4),
        "5": ([1,2,3,4,5], 5)
    }

    for (category, (nums, k)) in categories.items():

        # shallow item copy
        cpy = nums[:]

        sol.rotate(nums, k)

        print(f"{'category':<10} -> {category}")
        print(f"{'orig':<10} -> {cpy}")
        print(f"{'k':<10} -> {k}")
        print(f"{'shifted':<10} -> {nums}")
        print("\n----------------------\n")

    def rotate(self, nums: List[int], k: int) -> None:
        
        # Array Re Indexing On Extra Array

        # Substring Representation:
        #   - Each element moves to (i + k) % n
        #   - We avoid overwriting the original array
        #     before mapping is complete by moving nums to extra array

        n = len(nums)

        # If k is larger than n,
        # just mod it so its relative to the actual array size
        k = k % n

        # sc: O(n) for extra array
        rotatedCopy = [0] * n

        # Calculate all the new indexes and move nums
        # tc: iterate over n O(n)
        for indexCandidate in range(n):

            # Shift index i to its new index
            newIndex = (indexCandidate + k) % n

            # Put num in corresponding new index
            rotatedCopy[newIndex] = nums[indexCandidate]

        # Overwrite original array with shifted extra array
        # tc: iterate over n O(n)
        for i in range(n):
            nums[i] = rotatedCopy[i]

        # overall: tc O(n)
        # overall: sc O(n)

    def rotate(self, nums: List[int], k: int) -> None:
        
        # Cyclic Replacements (Modular Cycle Traversal)

        # Idea:
        #   - Each element moves to (i + k) % n
        #   - This movement creates a cycle that we can follow as 
        #     we rotate elements 

        # Cycle:
        #   - Think of the cycle as a circle with nodes
        #   - We can step through the cycle, going from node to node
        #     as we place nums in their new nodes
        
        #   - The circle can have multiple cycles:
        #      0 => 2 => 0
        #      1 => 3 => 1
        #     or have a single cycle:
        #      0 => 2 => 4 => 1 => 3 => 0
        #     which is why we need the inner outer while loop to make sure:
        #        - complete the current cycle
        #        - complete all cycles
        
        n = len(nums)

        # If k is larger than n,
        # just mod it so its relative to the actual array size
        k = k % n

        # Total num of elements we have moved to new indexes
        numsMoved = 0  

        # Start of the first cycle
        currCycleEntryPoint = 0

        # tc: shift n elements O(n)
        while numsMoved < n:

            # First shifted index will be the index at the cycle entry point
            indexToShift = currCycleEntryPoint

            # First carried value will be the value at the cycle entry point
            carriedValue = nums[currCycleEntryPoint]

            # While we have not reached the beginning of the current cycle
            while True:

                # Cycle Formula:

                # shift the index 
                shiftedIndex = indexToShift + k
                
                # make sure it does go out of bounds
                inBoundsIndex = shiftedIndex % n

                # Placed num we are carrying into its new rotated position
                # The displaced number becomes our new carry
                nums[inBoundsIndex], carriedValue = carriedValue, nums[inBoundsIndex]

                # Set new index, as next index we are calculating the new position for
                indexToShift = inBoundsIndex

                # Number of numbers we have replaced
                numsMoved += 1

                # If we returned to the current cycle entry point, cycle is complete
                if currCycleEntryPoint == indexToShift:
                    break

            # Move to the next potential cycle entry point
            currCycleEntryPoint += 1

        # overall: tc O(n)
        # overall: sc O(1)

    def rotate(self, nums: List[int], k: int) -> None:

        # Two Pointers (Reversal Trick Technique)

        # Key Insight:
        #   Reverse entire array
        #         [7,6,5,4,3,2,1]
        #   Reverse first k elements
        #         [5,6,7,4,3,2,1]
        #   Reverse remaining n-k elements
        #         [5,6,7,1,2,3,4]

        # This achieves rotation in-place.

        n = len(nums)

        # If k is larger than n,
        # just mod it so its relative to the actual array size
        k = k % n
        
        # Helper: reverses an array
        def reverse(left, right) -> None:

            # tc: iterate over n O(n)
            while left < right:

                # swap elements at index
                nums[left], nums[right] = nums[right], nums[left]

                # shrink towards middle
                left += 1
                right -= 1

        # Reverse entire array
        reverse(0, n - 1)

        # Reverse first [0, k] elements
        reverse(0, k - 1)

        # Reverse second [k, n] elements
        reverse(k, n - 1)

        # overall: tc O(n)
        # overall: sc O(1)