"""
## LC 881 — Boats to Save People

You are given an array `people` where `people[i]` is the weight of the `i`-th person,
and an infinite number of boats where each boat can carry at most two people at a time,
provided the sum of their weights is at most `limit`.
Return the minimum number of boats to carry every given person.

### Examples

```text
Input:  people = [1, 2], limit = 3
Output: 1

Input:  people = [3, 2, 2, 1], limit = 3
Output: 3

Input:  people = [3, 5, 3, 4], limit = 5
Output: 4
```

### Constraints

- 1 <= people.length <= 5 * 10^4
- 1 <= people[i] <= limit <= 3 * 10^4
"""
from typing import List


class Solution:
    def method_brute_force(self, people: List[int], limit: int) -> int:
        """O(n^2) time | O(n) space — greedy without sorting"""
        # Greedily pair heaviest with lightest that fits — O(n^2) without sorting
        remaining = people[:]
        boats = 0
        while remaining:
            heaviest = max(remaining)
            remaining.remove(heaviest)
            boats += 1
            for i, w in enumerate(remaining):
                if heaviest + w <= limit:
                    remaining.pop(i)
                    break
        return boats

    def numRescueBoats(self, people: List[int], limit: int) -> int:
        """O(n log n) time | O(1) space"""
        # Sort so lightest and heaviest are at opposite ends
        # Always send the heaviest person; pair with lightest if they fit together
        # Each iteration uses exactly one boat — count boats until all rescued
        people.sort()
        lo, hi = 0, len(people) - 1
        boats = 0
        while lo <= hi:
            if people[lo] + people[hi] <= limit:
                lo += 1
            hi -= 1
            boats += 1
        return boats


if __name__ == "__main__":
    sol = Solution()
    print(sol.numRescueBoats([1, 2], 3))          # 1
    print(sol.numRescueBoats([3, 2, 2, 1], 3))    # 3
    print(sol.numRescueBoats([3, 5, 3, 4], 5))    # 4

"""
## LC 11 — Container With Most Water

You are given an integer array `height` of length `n`. There are `n` vertical lines
drawn such that the two endpoints of the `i`-th line are `(i, 0)` and `(i, height[i])`.
Find two lines that together with the x-axis form a container that holds the most water.
Return the maximum amount of water a container can store.

### Examples

```text
Input:  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

Input:  height = [1, 1]
Output: 1
```

### Constraints

- n == height.length
- 2 <= n <= 10^5
- 0 <= height[i] <= 10^4
"""
from typing import List


class Solution:
    def method_brute_force(self, height: List[int]) -> int:
        """O(n^2) time | O(1) space"""
        # Try all pairs of lines — O(n^2)
        max_water = 0
        n = len(height)
        for i in range(n):
            for j in range(i + 1, n):
                max_water = max(max_water, min(height[i], height[j]) * (j - i))
        return max_water

    def maxArea(self, height: List[int]) -> int:
        """O(n) time | O(1) space"""
        # Start with widest container; move the shorter wall inward
        # Moving the taller wall can only decrease area, so always move shorter
        lo, hi = 0, len(height) - 1
        max_water = 0
        while lo < hi:
            max_water = max(max_water, min(height[lo], height[hi]) * (hi - lo))
            if height[lo] < height[hi]:
                lo += 1
            else:
                hi -= 1
        return max_water


if __name__ == "__main__":
    sol = Solution()
    print(sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
    print(sol.maxArea([1, 1]))                         # 1

"""
## LC 18 — 4Sum

Given an array `nums` of `n` integers and an integer `target`, return all unique
quadruplets `[nums[a], nums[b], nums[c], nums[d]]` such that all indices are distinct
and `nums[a] + nums[b] + nums[c] + nums[d] == target`.

### Examples

```text
Input:  nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Input:  nums = [2, 2, 2, 2, 2], target = 8
Output: [[2, 2, 2, 2]]
```

### Constraints

- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
"""
from typing import List


class Solution:
    def method_brute_force(self, nums: List[int], target: int) -> List[List[int]]:
        """O(n^4) time | O(n) space (result)"""
        # Try all quadruplets — O(n^4); use set to deduplicate
        n = len(nums)
        result = set()
        for a in range(n):
            for b in range(a + 1, n):
                for c in range(b + 1, n):
                    for d in range(c + 1, n):
                        if nums[a] + nums[b] + nums[c] + nums[d] == target:
                            result.add(tuple(sorted([nums[a], nums[b], nums[c], nums[d]])))
        return [list(t) for t in result]

    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        """O(n^3) time | O(1) extra space"""
        # Sort, fix two outer indices i and j, then use two pointers for the rest
        # Skip duplicate values at each level to avoid duplicate quadruplets
        # Inner two-pointer converges: move lo right if sum too small, hi left if too large
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                lo, hi = j + 1, n - 1
                while lo < hi:
                    s = nums[i] + nums[j] + nums[lo] + nums[hi]
                    if s == target:
                        result.append([nums[i], nums[j], nums[lo], nums[hi]])
                        while lo < hi and nums[lo] == nums[lo + 1]:
                            lo += 1
                        while lo < hi and nums[hi] == nums[hi - 1]:
                            hi -= 1
                        lo += 1
                        hi -= 1
                    elif s < target:
                        lo += 1
                    else:
                        hi -= 1
        return result


if __name__ == "__main__":
    sol = Solution()
    print(sol.fourSum([1, 0, -1, 0, -2, 2], 0))  # [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
    print(sol.fourSum([2, 2, 2, 2, 2], 8))        # [[2,2,2,2]]

"""
## LC 88: Merge Sorted Array

You are given two integer arrays `nums1` and `nums2`, sorted in non-decreasing
order, and two integers `m` and `n`, representing the number of elements in
`nums1` and `nums2` respectively.

Merge `nums2` into `nums1` as one sorted array in-place. `nums1` has a length
of `m + n`, where the last `n` elements are set to `0` and should be ignored.

### Examples

```text
Input:  nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Input:  nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Input:  nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
```

### Constraints

- `nums1.length == m + n`
- `nums2.length == n`
- `0 <= m, n <= 200`
- `1 <= m + n`
- `-10^9 <= nums1[i], nums2[j] <= 10^9`
"""
from typing import List


class Solution:
    def method_merge_sort(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """O((m+n) log(m+n)) time, O(n) space."""
        # Copy nums2 into the spare space of nums1, then sort — O((m+n) log(m+n))
        nums1[m:] = nums2[:n]
        nums1.sort()

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """O(m+n) time, O(1) space — fill from the end."""
        # Fill from the END to avoid overwriting unprocessed elements in nums1
        # Compare largest remaining from each array, place the bigger one at k
        # Remaining nums2 elements (if any) are copied directly — nums1 elements already in place
        i, j, k = m - 1, n - 1, m + n - 1
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1


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

    nums1 = [1, 2, 3, 0, 0, 0]
    sol.merge(nums1, 3, [2, 5, 6], 3)
    assert nums1 == [1, 2, 2, 3, 5, 6], f"Failed: {nums1}"

    nums1 = [1]
    sol.merge(nums1, 1, [], 0)
    assert nums1 == [1], f"Failed: {nums1}"

    nums1 = [0]
    sol.merge(nums1, 0, [1], 1)
    assert nums1 == [1], f"Failed: {nums1}"

    print("All tests passed.")

"""
## LC 1768: Merge Strings Alternately

You are given two strings `word1` and `word2`. Merge the strings by adding letters
in alternating order, starting with `word1`. If a string is longer than the other,
append the additional letters onto the end of the merged string.

Return the merged string.

### Examples

```text
Input:  word1 = "abc", word2 = "pqr"
Output: "apbqcr"

Input:  word1 = "ab", word2 = "pqrs"
Output: "apbqrs"

Input:  word1 = "abcd", word2 = "pq"
Output: "apbqcd"
```

### Constraints

- `1 <= word1.length, word2.length <= 100`
- `word1` and `word2` consist of lowercase English letters.
"""


class Solution:
    def method_index(self, word1: str, word2: str) -> str:
        """O(n+m) time — index-based loop."""
        # Use a single index up to max length, conditionally append from each string
        result = []
        n = max(len(word1), len(word2))
        for i in range(n):
            if i < len(word1):
                result.append(word1[i])
            if i < len(word2):
                result.append(word2[i])
        return "".join(result)

    def mergeAlternately(self, word1: str, word2: str) -> str:
        """O(n+m) time, O(1) extra space (excluding output)."""
        # Advance both pointers together while both strings have characters
        # Append remaining tail of whichever string is longer
        result = []
        i, j = 0, 0
        while i < len(word1) and j < len(word2):
            result.append(word1[i])
            result.append(word2[j])
            i += 1
            j += 1
        result.append(word1[i:])
        result.append(word2[j:])
        return "".join(result)


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

    assert sol.mergeAlternately("abc", "pqr") == "apbqcr"
    assert sol.mergeAlternately("ab", "pqrs") == "apbqrs"
    assert sol.mergeAlternately("abcd", "pq") == "apbqcd"

    print("All tests passed.")

"""
## LC 26: Remove Duplicates from Sorted Array

Given an integer array `nums` sorted in non-decreasing order, remove the
duplicates in-place such that each unique element appears only once. The
relative order of the elements should be kept the same. Return the number
of unique elements `k`.

The first `k` elements of `nums` should hold the unique values. The remaining
elements do not matter.

### Examples

```text
Input:  nums = [1,1,2]
Output: 2, nums = [1,2,_]

Input:  nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
```

### Constraints

- `1 <= nums.length <= 3 * 10^4`
- `-100 <= nums[i] <= 100`
- `nums` is sorted in non-decreasing order.
"""
from typing import List


class Solution:
    def method_set(self, nums: List[int]) -> int:
        """O(n) time, O(n) space."""
        # Collect unique elements via set, sort them, overwrite nums in-place
        unique = sorted(set(nums))
        for i, v in enumerate(unique):
            nums[i] = v
        return len(unique)

    def removeDuplicates(self, nums: List[int]) -> int:
        """O(n) time, O(1) space."""
        # k is the write pointer for unique elements
        # Since array is sorted, a new unique element is found when nums[i] != nums[i-1]
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
        return k


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

    nums = [1, 1, 2]
    k = sol.removeDuplicates(nums)
    assert k == 2 and nums[:k] == [1, 2], f"Failed: k={k}, nums={nums}"

    nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    k = sol.removeDuplicates(nums)
    assert k == 5 and nums[:k] == [0, 1, 2, 3, 4], f"Failed: k={k}, nums={nums}"

    nums = [1]
    k = sol.removeDuplicates(nums)
    assert k == 1 and nums[:k] == [1], f"Failed: k={k}, nums={nums}"

    print("All tests passed.")

"""
## LC 344: Reverse String

Write a function that reverses a string. The input string is given as an array
of characters `s`. You must do this by modifying the input array in-place with
O(1) extra memory.

### Examples

```text
Input:  s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Input:  s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
```

### Constraints

- `1 <= s.length <= 10^5`
- `s[i]` is a printable ASCII character.
"""
from typing import List


class Solution:
    def method_pythonic(self, s: List[str]) -> None:
        """O(n) time, O(n) space (slice creates a copy)."""
        # Slice reversal creates a copy and assigns back — O(n) space
        s[:] = s[::-1]

    def reverseString(self, s: List[str]) -> None:
        """O(n) time, O(1) space."""
        # Swap characters from both ends moving inward — O(1) space
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1


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

    s = ["h", "e", "l", "l", "o"]
    sol.reverseString(s)
    assert s == ["o", "l", "l", "e", "h"], f"Failed: {s}"

    s = ["H", "a", "n", "n", "a", "h"]
    sol.reverseString(s)
    assert s == ["h", "a", "n", "n", "a", "H"], f"Failed: {s}"

    s = ["a"]
    sol.reverseString(s)
    assert s == ["a"], f"Failed: {s}"

    print("All tests passed.")

"""
## LC 189 — Rotate Array

Given an integer array `nums`, rotate the array to the right by `k` steps,
where `k` is non-negative. Modify `nums` in-place.

### Examples

```text
Input:  nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]

Input:  nums = [-1, -100, 3, 99], k = 2
Output: [3, 99, -1, -100]
```

### Constraints

- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
"""
from typing import List


class Solution:
    def method_brute_force(self, nums: List[int], k: int) -> None:
        """O(n*k) time | O(1) space — rotate one step at a time"""
        # Rotate one step at a time by shifting all elements right — O(n*k)
        n = len(nums)
        k %= n
        for _ in range(k):
            last = nums[-1]
            for i in range(n - 1, 0, -1):
                nums[i] = nums[i - 1]
            nums[0] = last

    def method_extra_array(self, nums: List[int], k: int) -> None:
        """O(n) time | O(n) space"""
        # Slice the last k elements to front, rest follows — O(n) space
        n = len(nums)
        k %= n
        tmp = nums[-k:] + nums[:-k]
        nums[:] = tmp

    def rotate(self, nums: List[int], k: int) -> None:
        """O(n) time | O(1) space — reverse three times"""
        # Reverse entire array, then reverse first k, then reverse rest k..n-1
        # Three reversals achieve a rotation without extra space
        n = len(nums)
        k %= n

        def reverse(lo: int, hi: int) -> None:
            while lo < hi:
                nums[lo], nums[hi] = nums[hi], nums[lo]
                lo += 1
                hi -= 1

        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)


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

    nums = [1, 2, 3, 4, 5, 6, 7]
    sol.rotate(nums, 3)
    print(nums)  # [5, 6, 7, 1, 2, 3, 4]

    nums = [-1, -100, 3, 99]
    sol.rotate(nums, 2)
    print(nums)  # [3, 99, -1, -100]

"""
## LC 15 — 3Sum

Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]`
such that `i != j`, `i != k`, `j != k`, and `nums[i] + nums[j] + nums[k] == 0`.
The solution set must not contain duplicate triplets.

### Examples

```text
Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Input:  nums = [0, 1, 1]
Output: []

Input:  nums = [0, 0, 0]
Output: [[0, 0, 0]]
```

### Constraints

- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
"""
from typing import List


class Solution:
    def method_brute_force(self, nums: List[int]) -> List[List[int]]:
        """O(n^3) time | O(n) space (result)"""
        # Try all triplets — O(n^3); use a set to avoid duplicate triplets
        n = len(nums)
        result = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        result.add(tuple(sorted([nums[i], nums[j], nums[k]])))
        return [list(t) for t in result]

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """O(n^2) time | O(1) extra space"""
        # Sort first so we can use two pointers and skip duplicates easily
        # Fix one element i, then use two pointers lo/hi for the remaining pair
        # Skip duplicate values of i, lo, hi to avoid duplicate triplets
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s == 0:
                    result.append([nums[i], nums[lo], nums[hi]])
                    while lo < hi and nums[lo] == nums[lo + 1]:
                        lo += 1
                    while lo < hi and nums[hi] == nums[hi - 1]:
                        hi -= 1
                    lo += 1
                    hi -= 1
                elif s < 0:
                    lo += 1
                else:
                    hi -= 1
        return result


if __name__ == "__main__":
    sol = Solution()
    print(sol.threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2],[-1,0,1]]
    print(sol.threeSum([0, 1, 1]))               # []
    print(sol.threeSum([0, 0, 0]))               # [[0,0,0]]

"""
## LC 42 — Trapping Rain Water

Given `n` non-negative integers representing an elevation map where the width of each
bar is 1, compute how much water it can trap after raining.

### Examples

```text
Input:  height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Input:  height = [4, 2, 0, 3, 2, 5]
Output: 9
```

### Constraints

- n == height.length
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5
"""
from typing import List


class Solution:
    def method_brute_force(self, height: List[int]) -> int:
        """O(n^2) time | O(1) space — for each bar scan left and right max"""
        # For each bar, scan left and right to find max heights — O(n^2)
        n = len(height)
        water = 0
        for i in range(n):
            left_max = max(height[:i + 1])
            right_max = max(height[i:])
            water += min(left_max, right_max) - height[i]
        return water

    def method_prefix_arrays(self, height: List[int]) -> int:
        """O(n) time | O(n) space"""
        # Precompute left_max[i] and right_max[i] in two passes
        # Water at i = min(left_max[i], right_max[i]) - height[i]
        n = len(height)
        left_max = [0] * n
        right_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
        return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

    def trap(self, height: List[int]) -> int:
        """O(n) time | O(1) space"""
        # Two-pointer: process the side with the smaller max height
        # The shorter side's water level is fully determined by its own max
        # If current bar >= its side's max, update max; else accumulate water
        lo, hi = 0, len(height) - 1
        left_max = right_max = water = 0
        while lo <= hi:
            if height[lo] <= height[hi]:
                if height[lo] >= left_max:
                    left_max = height[lo]
                else:
                    water += left_max - height[lo]
                lo += 1
            else:
                if height[hi] >= right_max:
                    right_max = height[hi]
                else:
                    water += right_max - height[hi]
                hi -= 1
        return water


if __name__ == "__main__":
    sol = Solution()
    print(sol.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))  # 6
    print(sol.trap([4, 2, 0, 3, 2, 5]))                      # 9

"""
## LC 167: Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers `numbers` that is already sorted in
non-decreasing order, find two numbers such that they add up to a specific
`target` number. Return the indices of the two numbers as an integer array
`[index1, index2]` where `1 <= index1 < index2 <= numbers.length`.

The solution must use only constant extra space.

### Examples

```text
Input:  numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 + 7 = 9.

Input:  numbers = [2,3,4], target = 6
Output: [1,3]

Input:  numbers = [-1,0], target = -1
Output: [1,2]
```

### Constraints

- `2 <= numbers.length <= 3 * 10^4`
- `-1000 <= numbers[i] <= 1000`
- `numbers` is sorted in non-decreasing order.
- The tests are generated such that there is exactly one solution.
- You may not use the same element twice.
"""
from typing import List
import bisect


class Solution:
    def method_brute_force(self, numbers: List[int], target: int) -> List[int]:
        """O(n^2) time, O(1) space."""
        # Check all pairs — O(n^2); array is sorted but we ignore that here
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []

    def method_binary_search(self, numbers: List[int], target: int) -> List[int]:
        """O(n log n) time, O(1) space."""
        # For each element, binary search for its complement in the rest
        for i in range(len(numbers)):
            complement = target - numbers[i]
            j = bisect.bisect_left(numbers, complement, i + 1)
            if j < len(numbers) and numbers[j] == complement:
                return [i + 1, j + 1]
        return []

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        """O(n) time, O(1) space."""
        # Sorted array: if sum too small move left pointer right, if too large move right left
        # Converge until the exact target sum is found
        l, r = 0, len(numbers) - 1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:
                return [l + 1, r + 1]
            elif s < target:
                l += 1
            else:
                r -= 1
        return []


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

    assert sol.twoSum([2, 7, 11, 15], 9) == [1, 2]
    assert sol.twoSum([2, 3, 4], 6) == [1, 3]
    assert sol.twoSum([-1, 0], -1) == [1, 2]
    assert sol.twoSum([1, 2, 3, 4, 4, 9, 56, 90], 8) == [4, 5]

    print("All tests passed.")

"""
## LC 125: Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase
letters and removing all non-alphanumeric characters, it reads the same forward
and backward.

Given a string `s`, return `true` if it is a palindrome, or `false` otherwise.

### Examples

```text
Input:  s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Input:  s = "race a car"
Output: false

Input:  s = " "
Output: true
```

### Constraints

- `1 <= s.length <= 2 * 10^5`
- `s` consists only of printable ASCII characters.
"""


class Solution:
    def method_filter(self, s: str) -> bool:
        """O(n) time, O(n) space."""
        # Strip non-alphanumeric chars and lowercase, then compare to reverse
        filtered = [c.lower() for c in s if c.isalnum()]
        return filtered == filtered[::-1]

    def isPalindrome(self, s: str) -> bool:
        """O(n) time, O(1) space."""
        # Skip non-alphanumeric chars from both ends before comparing
        # Move both pointers inward; mismatch means not a palindrome
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True


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

    assert sol.isPalindrome("A man, a plan, a canal: Panama") is True
    assert sol.isPalindrome("race a car") is False
    assert sol.isPalindrome(" ") is True
    assert sol.isPalindrome("0P") is False

    print("All tests passed.")

"""
## LC 680: Valid Palindrome II

Given a string `s`, return `true` if the `s` can be palindrome after deleting
at most one character from it.

### Examples

```text
Input:  s = "aba"
Output: true

Input:  s = "abca"
Output: true
Explanation: Delete 'c' to get "aba".

Input:  s = "abc"
Output: false
```

### Constraints

- `1 <= s.length <= 10^5`
- `s` consists of lowercase English letters.
"""


class Solution:
    def method_brute_force(self, s: str) -> bool:
        """O(n^2) time — try removing each character."""
        # Try removing each character and check if result is palindrome
        def is_palindrome(t: str) -> bool:
            return t == t[::-1]

        if is_palindrome(s):
            return True
        for i in range(len(s)):
            if is_palindrome(s[:i] + s[i + 1:]):
                return True
        return False

    def validPalindrome(self, s: str) -> bool:
        """O(n) time, O(1) space."""
        # Walk inward until a mismatch; then try skipping left or right char
        # If either skip produces a palindrome, one deletion suffices
        def is_palindrome(l: int, r: int) -> bool:
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        l, r = 0, len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return is_palindrome(l + 1, r) or is_palindrome(l, r - 1)
            l += 1
            r -= 1
        return True


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

    assert sol.validPalindrome("aba") is True
    assert sol.validPalindrome("abca") is True
    assert sol.validPalindrome("abc") is False
    assert sol.validPalindrome("a") is True
    assert sol.validPalindrome("deeee") is True

    print("All tests passed.")