# ord() gives the ASCII (Unicode) value of a character
print(ord('a'))   # 97
print(ord('z'))   # 122
print(ord('A'))   # 65
print(ord('0'))   # 48

# chr() gives the character for a given value
print(chr(97))    # 'a'
print(chr(65))    # 'A'

# A very common DSA trick: get the position of a letter in the alphabet
# 'a' is position 0, 'b' is position 1, etc.
def letter_position(c):
    return ord(c) - ord('a')

print(letter_position('a'))  # 0
print(letter_position('e'))  # 4
print(letter_position('z'))  # 25

s = "hello"       # ASCII characters -- each stored in 1 byte internally
s = "こんにちは"    # Japanese characters -- Unicode
s = "مرحبا"       # Arabic -- Unicode
s = "🐍"          # Emoji -- Unicode

# len() counts characters, not bytes
print(len("hello"))    # 5
print(len("こんにちは"))  # 5

s = "hello"
print(id(s))       # memory address of s, e.g. 140234567890

s = s + " world"   # this does NOT modify "hello"
                   # it creates a NEW string "hello world" and s now points to it
print(id(s))       # different memory address -- it is a new object

# You cannot modify a character in place -- this raises a TypeError
s = "hello"
s[0] = "H"         # TypeError: 'str' object does not support item assignment

# List -- mutable, can be changed in place
nums = [1, 2, 3]
nums[0] = 99       # works fine
print(nums)        # [99, 2, 3]

# String -- immutable, cannot be changed in place
s = "hello"
s[0] = "H"         # TypeError

# The wrong way -- O(n^2)
# Each += creates a brand new string and copies everything
result = ""
for char in ["h", "e", "l", "l", "o"]:
    result += char   # creates a new string each time

# The right way -- O(n)
# Accumulate parts in a list, join once at the end
parts = []
for char in ["h", "e", "l", "l", "o"]:
    parts.append(char)    # O(1) append
result = "".join(parts)   # one O(n) join at the end

print(result)  # "hello"

s = "  Hello, World!  "

# Case conversion
print(s.lower())          # "  hello, world!  "
print(s.upper())          # "  HELLO, WORLD!  "

# Whitespace removal
print(s.strip())          # "Hello, World!"
print(s.lstrip())         # "Hello, World!  "  (left only)
print(s.rstrip())         # "  Hello, World!"  (right only)

# Search and check
print(s.find("World"))    # 9  (index of first occurrence, -1 if not found)
print(s.count("l"))       # 3  (count of occurrences)
print(s.startswith("  H"))  # True
print(s.endswith("!  "))    # True

# Split and join
words = "apple,banana,cherry".split(",")
print(words)              # ['apple', 'banana', 'cherry']
print(",".join(words))    # "apple,banana,cherry"

sentence = "hello world python"
print(sentence.split())   # ['hello', 'world', 'python'] (splits on whitespace)

# Replace
print("hello world".replace("world", "python"))  # "hello python"

# Check character types
print("abc".isalpha())    # True  -- all alphabetic
print("123".isdigit())    # True  -- all digits
print("abc123".isalnum()) # True  -- all alphanumeric
print("  ".isspace())     # True  -- all whitespace
print("Hello".islower())  # False
print("Hello".isupper())  # False
print("HELLO".isupper())  # True

s = "hello"

# Indexing -- O(1)
print(s[0])    # 'h'
print(s[-1])   # 'o'

# Slicing -- O(k)
print(s[1:4])  # 'ell'
print(s[::-1]) # 'olleh'  -- reversed string

# Iterating
for char in s:
    print(char)

# Enumerate -- gives index and character
for i, char in enumerate(s):
    print(i, char)
# 0 h
# 1 e
# 2 l
# 3 l
# 4 o

# Convert to list if you need to modify
chars = list(s)     # ['h', 'e', 'l', 'l', 'o']
chars[0] = 'H'      # now you can modify
result = "".join(chars)  # 'Hello'

left, right = 0, len(s) - 1

while left < right:
    # compare s[left] and s[right]
    # move pointers based on the condition
    left += 1
    right -= 1

def valid_palindrome(s: str) -> bool:
    """
    Two pointers from both ends.
    On first mismatch, try skipping left character or right character.
    If either skip produces a palindrome, return True.

    Time complexity:  O(n) -- we scan the string at most twice
    Space complexity: O(1) -- only index variables, no new strings stored
                             (the is_palindrome check uses indices, not slices)
    """

    def is_palindrome(s, left, right):
        """Check if s[left..right] is a palindrome using two pointers."""
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            # Mismatch -- try skipping left character or right character
            # If either works, we can make a palindrome with one deletion
            return (is_palindrome(s, left + 1, right) or
                    is_palindrome(s, left, right - 1))
        left += 1
        right -= 1

    return True  # no mismatch found -- already a palindrome

# Test
print(valid_palindrome("abca"))   # True
print(valid_palindrome("abc"))    # False
print(valid_palindrome("racecar")) # True (already a palindrome)
print(valid_palindrome("deeee"))  # True (remove one 'e')

def reverse_string(s: list) -> None:
    """
    Swap characters from both ends moving inward.
    Modifies the list in place -- nothing is returned.

    Time complexity:  O(n) -- each character is visited once
    Space complexity: O(1) -- swapping in place, no extra memory
    """
    left, right = 0, len(s) - 1

    while left < right:
        # Swap characters at left and right
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

# Test
s = ['h','e','l','l','o']
reverse_string(s)
print(s)  # ['o', 'l', 'l', 'e', 'h']

from collections import defaultdict

def sliding_window_string(s):
    left = 0
    window = defaultdict(int)   # track character counts in the window
    result = 0

    for right in range(len(s)):
        # Expand: add s[right] to the window
        window[s[right]] += 1

        # Shrink: while window violates the condition, move left forward
        while # window condition is violated:
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1

        # Window is now valid -- update result
        result = max(result, right - left + 1)

    return result

def length_of_longest_substring(s: str) -> int:
    """
    Sliding window with a set tracking characters in the current window.
    Expand right, shrink left when a duplicate is found.

    Time complexity:  O(n) -- each character is added and removed at most once
    Space complexity: O(min(n, a)) -- a is the size of the character set (26 for
                                      lowercase letters, 128 for ASCII)
    """
    char_set = set()    # characters currently in the window
    left = 0
    max_length = 0

    for right in range(len(s)):
        # Shrink window from left until s[right] is no longer a duplicate
        while s[right] in char_set:
            char_set.remove(s[left])   # remove leftmost character
            left += 1                  # shrink window

        # Now s[right] is not in the window -- safe to add it
        char_set.add(s[right])

        # Update maximum length
        max_length = max(max_length, right - left + 1)

    return max_length

# Test
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))      # 1
print(length_of_longest_substring("pwwkew"))     # 3
print(length_of_longest_substring(""))           # 0

from collections import Counter

def min_window(s: str, t: str) -> str:
    """
    Sliding window with two frequency maps.
    Expand right until window contains all of t.
    Then shrink left to find the minimum valid window.
    Repeat until right reaches the end.

    Time complexity:  O(n + m) -- n = len(s), m = len(t)
                                  each character in s is added and removed at most once
    Space complexity: O(m) -- the frequency maps store at most m distinct characters
    """
    if not t or not s:
        return ""

    # Frequency map for characters we need
    t_count = Counter(t)

    # Number of unique characters in t that we still need to satisfy
    required = len(t_count)

    # Sliding window pointers and state
    left = 0
    formed = 0          # how many unique chars in t are currently satisfied in window
    window_count = {}   # frequency of characters in current window

    # Result: (window length, left index, right index)
    result = float('inf'), 0, 0

    for right in range(len(s)):
        # Add s[right] to the window
        char = s[right]
        window_count[char] = window_count.get(char, 0) + 1

        # Check if this character's frequency now satisfies t's requirement
        if char in t_count and window_count[char] == t_count[char]:
            formed += 1

        # Try to shrink the window from left while it is still valid
        while left <= right and formed == required:
            # This window is valid -- update result if it is smaller
            window_length = right - left + 1
            if window_length < result[0]:
                result = (window_length, left, right)

            # Remove s[left] from the window
            left_char = s[left]
            window_count[left_char] -= 1
            if left_char in t_count and window_count[left_char] < t_count[left_char]:
                formed -= 1   # window no longer satisfies this character
            left += 1

    if result[0] == float('inf'):
        return ""
    return s[result[1] : result[2] + 1]

# Test
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "a"))                # "a"
print(min_window("a", "aa"))               # ""

from collections import Counter

s = "hello"

# Approach 1: Counter (cleanest)
freq = Counter(s)
print(freq)   # Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})

# Approach 2: Dictionary manually
freq = {}
for char in s:
    freq[char] = freq.get(char, 0) + 1

# Approach 3: Fixed array of size 26 (most efficient for lowercase letters)
# Index 0 = 'a', index 1 = 'b', ..., index 25 = 'z'
freq = [0] * 26
for char in s:
    freq[ord(char) - ord('a')] += 1
print(freq)  # [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 2, 0, 0, 1, 0, ...]
#                              e        h           l  l        o

from collections import Counter

def is_anagram_v1(s: str, t: str) -> bool:
    """
    Approach 1: Sort both strings and compare.
    Two strings are anagrams if their sorted versions are equal.

    Time complexity:  O(n log n) -- sorting
    Space complexity: O(n) -- sorted() creates new strings
    """
    return sorted(s) == sorted(t)


def is_anagram_v2(s: str, t: str) -> bool:
    """
    Approach 2: Use Counter to compare frequency maps.
    Clean and Pythonic.

    Time complexity:  O(n + m) -- build two counters, compare them
    Space complexity: O(1) -- at most 26 distinct characters (lowercase letters)
    """
    return Counter(s) == Counter(t)


def is_anagram_v3(s: str, t: str) -> bool:
    """
    Approach 3: Single frequency array of size 26.
    Increment for each character in s, decrement for each in t.
    If all values are 0 at the end, they are anagrams.

    Time complexity:  O(n + m)
    Space complexity: O(1) -- fixed array of size 26 regardless of input size
    """
    if len(s) != len(t):
        return False

    count = [0] * 26

    for i in range(len(s)):
        count[ord(s[i]) - ord('a')] += 1   # increment for s
        count[ord(t[i]) - ord('a')] -= 1   # decrement for t

    # If all counts are 0, every character balanced out
    return all(c == 0 for c in count)

# Test all three
for fn in [is_anagram_v1, is_anagram_v2, is_anagram_v3]:
    print(fn("anagram", "nagaram"))  # True
    print(fn("rat", "car"))          # False

from collections import defaultdict

def group_anagrams(strs: list) -> list:
    """
    Sort each string to get a canonical key.
    All anagrams will have the same key.
    Group strings by their key using a defaultdict.

    Time complexity:  O(n * k log k) -- n strings, each of length at most k, sorted
    Space complexity: O(n * k) -- storing all strings in the groups dictionary
    """
    groups = defaultdict(list)

    for s in strs:
        key = tuple(sorted(s))   # sorted string as the key
                                  # use tuple because lists cannot be dict keys
        groups[key].append(s)

    return list(groups.values())

# Test
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

def group_anagrams_v2(strs: list) -> list:
    """
    Use a frequency array of size 26 as the key instead of sorting.
    This is slightly faster: O(n * k) instead of O(n * k log k).

    Time complexity:  O(n * k) -- n strings, each of length at most k
    Space complexity: O(n * k)
    """
    groups = defaultdict(list)

    for s in strs:
        # Build frequency array for this string
        count = [0] * 26
        for char in s:
            count[ord(char) - ord('a')] += 1

        key = tuple(count)   # convert to tuple so it can be used as a dict key
        groups[key].append(s)

    return list(groups.values())