Arrays & Strings

#Topic : Basics of Slicing and 2D Array Slicing
#Time  : O(k) -- proportional to the slicing length k
#Space : O(k) -- size of the slicing result copy


def demonstrate_1d_slicing() -> None:
    """1-dimensional list slicing example."""
    arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    print("=" * 45)
    print("Original Array:", arr)
    print("=" * 45)

    #Basic Slicing
    print("arr[2:6]   :", arr[2:6])     # [2, 3, 4, 5]
    print("arr[:4]    :", arr[:4])      # [0, 1, 2, 3]
    print("arr[6:]    :", arr[6:])      # [6, 7, 8, 9]
    print("arr[:]     :", arr[:])       #Full Copy

    #Negative Index
    print()
    print("arr[-1]    :", arr[-1])      #9 (last)
    print("arr[-3:]   :", arr[-3:])     # [7, 8, 9]
    print("arr[:-3]   :", arr[:-3])     # [0..6]

    #Step Slicing
    print()
    print("arr[::2]   :", arr[::2])     #Even Index
    print("arr[1::2]  :", arr[1::2])    #Odd Index
    print("arr[::-1]  :", arr[::-1])    #Reverse Copy
    print("arr[8:1:-2]:", arr[8:1:-2])  #Reverse Step


def demonstrate_copy_semantics() -> None:
    """Slicing creates a shallow copy."""
    print()
    print("=" * 45)
    print("Check Copy Semantics (Shallow Copy)")
    print("=" * 45)

    original = [10, 20, 30, 40, 50]
    sliced = original[1:4]     #[20, 30, 40] -- new list
    sliced[0] = 999

    print("original:", original)   #No change to original
    print("sliced  :", sliced)     # [999, 30, 40]
    print("-> The slicing result is an independent new list.")

    #Beware of shallow copy of nested lists
    nested = [[1, 2], [3, 4], [5, 6]]
    copied = nested[:]         #Outer list is copied
    copied[0][0] = 999         #Inner list is shared!
    print()
    print("nested (check inner sharing):", nested)   # [[999, 2], ...]
    print("-> Use copy.deepcopy() for nested lists.")


def demonstrate_2d_slicing() -> None:
    """Example of slicing a 2-dimensional array (a list of lists)."""
    print()
    print("=" * 45)
    print("2D Array Slicing")
    print("=" * 45)

    matrix = [
        [1,  2,  3,  4],
        [5,  6,  7,  8],
        [9, 10, 11, 12],
    ]

    print("Original Matrix:")
    for row in matrix:
        print(" ", row)

    #Row Slicing
    sub_rows = matrix[0:2]          #Rows 0~1
    print("\nmatrix[0:2] -- top 2 rows:")
    for row in sub_rows:
        print(" ", row)

    #Column Slicing (using list comprehension)
    col_2 = [row[2] for row in matrix]   #Column 2
    print("\nColumn 2:", col_2)

    #Submatrix
    sub_matrix = [row[1:3] for row in matrix[0:2]]
    print("\nmatrix[0:2][column 1:3] -- 2x2 submatrix:")
    for row in sub_matrix:
        print(" ", row)


def demonstrate_string_slicing() -> None:
    """String slicing -- strings are also sequences."""
    print()
    print("=" * 45)
    print("String Slicing")
    print("=" * 45)

    s = "Hello, World!"
    print("Original:", s)
    print("s[7:12] :", s[7:12])    # World
    print("s[:5]   :", s[:5])      # Hello
    print("s[::-1] :", s[::-1])    #Reverse
    print("s[::2]  :", s[::2])     #Step of 2


if __name__ == "__main__":
    demonstrate_1d_slicing()
    demonstrate_copy_semantics()
    demonstrate_2d_slicing()
    demonstrate_string_slicing()

#Topic : Practice of Major String Methods
#Time  : Refer to comments for each method
#Space : O(n) -- Most return a new string


def demo_split_join() -> None:
    """split / join methods -- O(n)."""
    print("=" * 50)
    print("split / join")
    print("=" * 50)

    sentence = "apple, banana, cherry, strawberry"
    fruits = sentence.split(",")        #Split by delimiter
    print("split(','):", fruits)

    #Without delimiter -- Split by whitespace, ignore consecutive spaces
    words = "  hello   world  ".split()
    print("split()   :", words)         # ['hello', 'world']

    #Difference between split(' ') vs split()
    spaced = "a  b".split(' ')          #Includes empty strings!
    print("split(' ') :", spaced)       # ['a', '', 'b']

    #join -- Convert list to string
    joined = " | ".join(fruits)
    print("join(' | '):", joined)

    #String accumulation -- join is O(n), repeated += is O(n^2)
    chars = list("Hello")
    fast = "".join(chars)               # O(n)
    print("''.join()  :", fast)


def demo_strip() -> None:
    """strip / lstrip / rstrip -- O(n)."""
    print()
    print("=" * 50)
    print("strip / lstrip / rstrip")
    print("=" * 50)

    s = "   Hello, Python!   "
    print("Original         :", repr(s))
    print("strip()      :", repr(s.strip()))
    print("lstrip()     :", repr(s.lstrip()))
    print("rstrip()     :", repr(s.rstrip()))

    #Remove specific character
    s2 = "###Important###"
    print("strip('#')   :", s2.strip("#"))


def demo_replace_find() -> None:
    """replace / find / count -- O(n)."""
    print()
    print("=" * 50)
    print("replace / find / count")
    print("=" * 50)

    text = "banana"
    print("Original :", text)
    print("replace('a','o')  :", text.replace("a", "o"))       # bonono
    print("replace('a','o',2):", text.replace("a", "o", 2))    #Up to 2 times

    #find -- Returns -1 if not found
    s = "Hello, World!"
    print("find('World') :", s.find("World"))   # 7
    print("find('xyz')   :", s.find("xyz"))     # -1
    print("index('World'):", s.index("World"))  #7 (Raises ValueError if not found)

    #rfind -- Search from right
    t = "abcabcabc"
    print("rfind('abc')  :", t.rfind("abc"))    # 6
    print("count('abc')  :", t.count("abc"))    # 3


def demo_case_methods() -> None:
    """upper / lower / capitalize / title -- O(n)."""
    print()
    print("=" * 50)
    print("Case conversion")
    print("=" * 50)

    s = "hello, World!"
    print("Original         :", s)
    print("upper()      :", s.upper())
    print("lower()      :", s.lower())
    print("capitalize() :", s.capitalize())   #Capitalize first letter only
    print("title()      :", s.title())        #Capitalize first letter of each word
    print("swapcase()   :", s.swapcase())     #Swap upper<->lower


def demo_check_methods() -> None:
    """isdigit / isalpha / isalnum / startswith / endswith -- O(n)."""
    print()
    print("=" * 50)
    print("Check methods")
    print("=" * 50)

    samples = ["hello", "Hello123", "12345", "  ", ""]
    for s in samples:
        print(
            f"{s!r:12} -> isalpha={str(s.isalpha()):5}"
            f" isdigit={str(s.isdigit()):5}"
            f" isalnum={str(s.isalnum()):5}"
        )

    url = "https://example.com"
    print()
    print("startswith('https'):", url.startswith("https"))
    print("endswith('.com')   :", url.endswith(".com"))


def demo_ord_chr() -> None:
    """ord / chr -- ASCII code conversion."""
    print()
    print("=" * 50)
    print("ord() / chr() -- ASCII code")
    print("=" * 50)

    print("ord('A') =", ord("A"), "/ ord('a') =", ord("a"), "/ ord('0') =", ord("0"))
    print("chr(65)  =", chr(65),  "/ chr(97)  =", chr(97),  "/ chr(48)  =", chr(48))

    #Alphabet index (0-based)
    for ch in "ace":
        idx = ord(ch) - ord("a")
        print(f"Alphabet index of '{ch}': {idx}")

    #Print all alphabets
    alphabet = [chr(ord("a") + i) for i in range(26)]
    print("Alphabets:", "".join(alphabet))


if __name__ == "__main__":
    demo_split_join()
    demo_strip()
    demo_replace_find()
    demo_case_methods()
    demo_check_methods()
    demo_ord_chr()

#Topic: Palindrome Check
#Time: O(n) -- proportional to the length of the string
#Space: O(n) naive / O(1) two-pointers


def is_palindrome_naive(s: str) -> bool:
    """Naive method: Compare with reversed string -- Time O(n), Space O(n)."""
    cleaned = s.lower()
    return cleaned == cleaned[::-1]


def is_palindrome_two_pointer(s: str) -> bool:
    """Two-pointer method -- Time O(n), Space O(1).

    Visualization:
        r a c e c a r
        ^           ^   r==r -> move
          ^       ^     a==a -> move
            ^   ^       c==c -> move
              ^ ^        e==e -> left >= right -> palindrome!"""
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True


def is_palindrome_alphanumeric(s: str) -> bool:
    """Palindrome considering only letters/numbers -- LeetCode 125 style.

    Example: 'A man, a plan, a canal: Panama' -> True
    Time O(n), Space O(1) (two pointers)."""
    left, right = 0, len(s) - 1
    while left < right:
        #Skip non-alphanumeric characters
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True


def longest_palindrome_expand(s: str) -> str:
    """Center Expansion (Expand Around Center) -- O(n^2) time, O(1) space."""
    def expand(left: int, right: int) -> str:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    best = ""
    for i in range(len(s)):
        odd = expand(i, i)          #Odd-length palindrome
        even = expand(i, i + 1)     #Even-length palindrome
        if len(odd) > len(best):
            best = odd
        if len(even) > len(best):
            best = even
    return best


if __name__ == "__main__":
    print("=" * 50)
    print("Palindrome check")
    print("=" * 50)

    test_cases = [
        ("racecar", True),
        ("hello",   False),
        ("abcba",   True),
        ("a",       True),
        ("",        True),
        ("abba",    True),
    ]

    print(f"{'String':15} {'Naive':8} {'Two-pointers':10}")
    print("-" * 35)
    for word, expected in test_cases:
        naive = is_palindrome_naive(word)
        tp    = is_palindrome_two_pointer(word)
        status = "OK" if naive == expected else "NG"
        print(f"{word!r:15} {str(naive):8} {str(tp):10} {status}")

    print()
    print("=" * 50)
    print("Alphanumeric palindrome")
    print("=" * 50)
    alphanums = [
        "A man, a plan, a canal: Panama",
        "race a car",
        " ",
    ]
    for s in alphanums:
        short = repr(s)[:35]
        print(f"{short:37} -> {is_palindrome_alphanumeric(s)}")

    print()
    print("=" * 50)
    print("Longest palindromic substring")
    print("=" * 50)
    for s in ["babad", "cbbd", "racecar", "abcba"]:
        result = longest_palindrome_expand(s)
        print(f"{s!r:10} -> {result!r}")

#Topic: Anagram Check
#Time: O(n) Counter method / O(n log n) sorted method
#Space: O(1) -- 26 fixed alphabets (Counter method)

from collections import Counter


def is_anagram_sorted(s: str, t: str) -> bool:
    """Comparison using sorted -- Time O(n log n), Space O(n).

    If two strings are sorted and are the same, they are anagrams."""
    return sorted(s.lower()) == sorted(t.lower())


def is_anagram_counter(s: str, t: str) -> bool:
    """Counter comparison -- Time O(n), Space O(1) (fixed 26 letters of the alphabet).

    Counter stores the frequency of each character in a dictionary."""
    return Counter(s.lower()) == Counter(t.lower())


def is_anagram_manual(s: str, t: str) -> bool:
    """Direct dictionary implementation -- Time O(n), Space O(1).

    How to implement without Counter."""
    if len(s) != len(t):
        return False

    freq: dict[str, int] = {}
    for ch in s.lower():
        freq[ch] = freq.get(ch, 0) + 1
    for ch in t.lower():
        freq[ch] = freq.get(ch, 0) - 1
        if freq[ch] < 0:
            return False
    return True


def is_anagram_array(s: str, t: str) -> bool:
    """Using an array (size 26) -- Time O(n), Space O(1).

    The fastest implementation when only lowercase letters are allowed."""
    if len(s) != len(t):
        return False

    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord("a")] += 1
    for ch in t:
        count[ord(ch) - ord("a")] -= 1
    return all(c == 0 for c in count)


def group_anagrams(words: list[str]) -> list[list[str]]:
    """Anagram Grouping -- Time O(n * k log k), Space O(n*k).

    k = maximum length of a word.
    Group using the sorted string as a key."""
    groups: dict[str, list[str]] = {}
    for word in words:
        key = "".join(sorted(word.lower()))
        groups.setdefault(key, []).append(word)
    return list(groups.values())


def find_all_anagram_positions(text: str, pattern: str) -> list[int]:
    """Return all anagram positions of a pattern in a string -- O(n) sliding window.

    A list of indices where an anagram of the pattern starts in the text."""
    result = []
    n, k = len(text), len(pattern)
    if k > n:
        return result

    pattern_cnt = Counter(pattern)
    window_cnt  = Counter(text[:k])

    if window_cnt == pattern_cnt:
        result.append(0)

    for i in range(1, n - k + 1):
        #Window sliding: remove left character, add right character
        left_char  = text[i - 1]
        right_char = text[i + k - 1]

        window_cnt[right_char] += 1
        window_cnt[left_char]  -= 1
        if window_cnt[left_char] == 0:
            del window_cnt[left_char]

        if window_cnt == pattern_cnt:
            result.append(i)

    return result


if __name__ == "__main__":
    print("=" * 50)
    print("Anagram check")
    print("=" * 50)

    pairs = [
        ("listen",  "silent",  True),
        ("hello",   "world",   False),
        ("rat",     "car",     False),
        ("anagram", "nagaram", True),
    ]

    print(f"{'s':12} {'t':12} {'sorted':8} {'counter':9} {'manual':8}")
    print("-" * 51)
    for s, t, expected in pairs:
        r1 = is_anagram_sorted(s, t)
        r2 = is_anagram_counter(s, t)
        r3 = is_anagram_manual(s, t)
        ok = "OK" if r1 == expected else "NG"
        print(f"{s:12} {t:12} {str(r1):8} {str(r2):9} {str(r3):8} {ok}")

    print()
    print("=" * 50)
    print("Anagram grouping")
    print("=" * 50)
    words = ["eat", "tea", "tan", "ate", "nat", "bat"]
    groups = group_anagrams(words)
    print("Input:", words)
    for g in groups:
        print(" ", sorted(g))

    print()
    print("=" * 50)
    print("Sliding window anagram position")
    print("=" * 50)
    text, pat = "cbaebabacd", "abc"
    positions = find_all_anagram_positions(text, pat)
    print(f"text={text!r}, pattern={pat!r}")
    print("Anagram start position:", positions)   # [0, 6]