"""
Arrays and Strings — learner-দের জন্য from-scratch implementation।

এখানে যা যা আছে:
  1. DynamicArray  — Python-এর list হাতে বানানো, যাতে তুমি নিজের চোখে
                     append / doubling / shifting-এর logic দেখতে পাও,
                     যা সাধারণত লুকানো থাকে।
  2. Pattern function গুলো — two pointers, sliding window, prefix sums,
                     rotation, frequency counting, string building, Kadane's।

সবকিছুতে শুধু Python-এর standard library ব্যবহার হয়েছে।
File টা সরাসরি চালাও:  python implementation.py
Demo-র সব assert pass করতে হবে; file টা ছোট একটা trace print করে যাতে
তুমি dynamic array-টাকে বড় হতে দেখতে পারো।
"""


class DynamicArray:
    """একটা simplified dynamic array (Python-এর list-এর মতো), fixed-size
    backing store-এর উপর বানানো।

    যে invariant গুলো আমরা সবসময় maintain করি:
      * 0 <= self._size <= self._capacity
      * self._data-র প্রথম `self._size`-টা slot-এ আসল element থাকে
      * self._size-এর পর থেকে slot গুলো spare room (None placeholder)
    """

    def __init__(self):
        self._capacity = 2          # ছোট দিয়ে শুরু, যাতে resize তাড়াতাড়ি ঘটে
        self._size = 0              # আমরা কয়টা আসল element ধরে আছি
        self._data = [None] * self._capacity   # backing store

    def __len__(self):
        return self._size

    def __getitem__(self, index):
        """O(1) access — backing store-এ স্রেফ arithmetic।"""
        if not 0 <= index < self._size:
            raise IndexError("index out of range")
        return self._data[index]

    def __setitem__(self, index, value):
        """O(1) update।"""
        if not 0 <= index < self._size:
            raise IndexError("index out of range")
        self._data[index] = value

    def append(self, value):
        """Amortized O(1): সাধারণত spare room-এ পড়ে; কালেভদ্রে resize।"""
        if self._size == self._capacity:
            self._resize(2 * self._capacity)   # সেই বিরল O(n) মুহূর্ত
        self._data[self._size] = value
        self._size += 1

    def _resize(self, new_capacity):
        """এই O(n) copy-টাই append-কে amortized O(1) বানায়।

        Doubling-টাই আসল: প্রতিবার +1 করে বাড়ালে PROTITA append-এই
        সবকিছু copy হতো, আর n-টা append-এর মোট খরচ হতো O(n^2)।
        """
        new_data = [None] * new_capacity
        for i in range(self._size):            # প্রতিটা element একবার copy
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

    def insert(self, index, value):
        """O(n): tail ডানে shift করে ফাঁক খোলো, তারপর value বসাও।"""
        if not 0 <= index <= self._size:
            raise IndexError("index out of range")
        if self._size == self._capacity:
            self._resize(2 * self._capacity)
        # SHESH থেকে শুরু করে ডানে shift করি, যাতে এখনো সরাতে হবে এমন
        # কোনো value কখনো overwrite না হয়।
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        self._data[index] = value
        self._size += 1

    def pop(self, index=None):
        """শেষটা pop করো O(1)-এ; মাঝেরটা pop করো O(n)-এ (ফাঁক বন্ধ করো)।"""
        if self._size == 0:
            raise IndexError("pop from empty array")
        if index is None:
            index = self._size - 1
        if not 0 <= index < self._size:
            raise IndexError("index out of range")
        value = self._data[index]
        for i in range(index, self._size - 1):  # tail বাঁয়ে shift করো
            self._data[i] = self._data[i + 1]
        self._size -= 1
        self._data[self._size] = None           # এখন-spare slot টা clear করো
        return value

    def capacity(self):
        """Expose করা আছে যাতে demo-তে doubling ঘটতে দেখা যায়।"""
        return self._capacity

    def to_list(self):
        return [self._data[i] for i in range(self._size)]


# ---------------------------------------------------------------------------
# Pattern function গুলো (প্রতিটা patterns.md-র একটা section-এর আয়না)
# ---------------------------------------------------------------------------

def reverse_in_place(a):
    """দুই প্রান্ত থেকে two pointers। O(n) time, O(1) extra space।"""
    left, right = 0, len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1
    return a


def rotate_right(a, k):
    """Triple-reversal trick দিয়ে ডানে k rotate। O(n)/O(1)।"""
    n = len(a)
    if n == 0:
        return a
    k %= n                       # n দিয়ে rotate মানে 0 দিয়ে rotate

    def rev(lo, hi):             # a[lo..hi] inclusive reverse করো
        while lo < hi:
            a[lo], a[hi] = a[hi], a[lo]
            lo += 1
            hi -= 1

    rev(0, n - 1)                # 1) সবকিছু reverse করো
    rev(0, k - 1)                # 2) প্রথম k-টা ঠিক করো
    rev(k, n - 1)                # 3) বাকিটা ঠিক করো
    return a


def pair_sum_sorted(a, target):
    """SORTED input-এ two pointers। (i, j) অথবা None return করে। O(n)।"""
    left, right = 0, len(a) - 1
    while left < right:
        s = a[left] + a[right]
        if s == target:
            return (left, right)
        if s < target:
            left += 1            # শুধু বড় left value-ই সাহায্য করতে পারে
        else:
            right -= 1           # শুধু ছোট right value-ই সাহায্য করতে পারে
    return None


def longest_unique_substring(s):
    """Sliding window: repeat ছাড়া longest run। O(n)।"""
    last_seen = {}               # char -> সবচেয়ে recent index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1     # duplicate-টা পার করে লাফ দাও
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best


def build_prefix(a):
    """prefix[i] = প্রথম i-টা element-এর sum; prefix[0] = 0। O(n)।"""
    prefix = [0]
    for x in a:
        prefix.append(prefix[-1] + x)
    return prefix


def range_sum(prefix, lo, hi):
    """আগে বানানো prefix array দিয়ে a[lo..hi] inclusive-এর sum। O(1)।"""
    return prefix[hi + 1] - prefix[lo]


def count_subarrays_with_sum(a, k):
    """Prefix sums + hash map: ঠিক k-তে sum হয় কয়টা subarray। O(n)।"""
    seen = {0: 1}                # prefix value -> কতবার দেখা গেছে
    running = 0
    count = 0
    for x in a:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count


def is_anagram(s, t):
    """Frequency counting: character multiset কি একই? O(n)।"""
    if len(s) != len(t):
        return False
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in t:
        if counts.get(ch, 0) == 0:
            return False
        counts[ch] -= 1
    return True


def run_length_encode(s):
    """String building-এর সঠিক উপায়: টুকরোগুলো list-এ, শেষে একটা join। O(n)।"""
    if not s:
        return ""
    parts = []
    run_char = s[0]
    run_len = 1
    for ch in s[1:]:
        if ch == run_char:
            run_len += 1
        else:
            parts.append(run_char + str(run_len))
            run_char, run_len = ch, 1
    parts.append(run_char + str(run_len))
    return "".join(parts)


def max_subarray_sum(a):
    """Kadane's algorithm। O(n)। a non-empty ধরে নেওয়া হয়েছে।

    best_end = ঠিক এখানে SHESH হওয়া subarray-র best sum।
    Negative best_end মানে মরা ওজন -> current element থেকে restart করো।
    """
    best_end = a[0]
    best = a[0]
    for x in a[1:]:
        best_end = max(x, best_end + x)   # run টা extend করো, নাহয় fresh শুরু
        best = max(best, best_end)
    return best


# ---------------------------------------------------------------------------
# Demo + tests
# ---------------------------------------------------------------------------

if __name__ == "__main__":
    print("=== DynamicArray: watch the capacity double ===")
    arr = DynamicArray()
    for value in [5, 2, 7, 9, 4]:
        arr.append(value)
        print(f"append({value}) -> size={len(arr)} capacity={arr.capacity()} "
              f"data={arr.to_list()}")
    assert arr.to_list() == [5, 2, 7, 9, 4]
    assert len(arr) == 5
    assert arr.capacity() == 8          # doubling-এ 2 -> 4 -> 8
    assert arr[2] == 7                  # O(1) access

    arr.insert(1, 8)                    # O(n) shift
    assert arr.to_list() == [5, 8, 2, 7, 9, 4]
    assert arr.pop() == 4               # O(1) end pop
    assert arr.pop(1) == 8              # O(n) middle pop
    assert arr.to_list() == [5, 2, 7, 9]
    arr[0] = 50
    assert arr.to_list() == [50, 2, 7, 9]

    print("\n=== Pattern functions ===")
    assert reverse_in_place([1, 2, 3, 4, 5]) == [5, 4, 3, 2, 1]
    assert reverse_in_place([]) == []

    assert rotate_right([1, 2, 3, 4, 5], 2) == [4, 5, 1, 2, 3]
    assert rotate_right([1, 2, 3], 0) == [1, 2, 3]
    assert rotate_right([1, 2, 3], 7) == [3, 1, 2]   # 7 % 3 == 1

    assert pair_sum_sorted([1, 3, 4, 6, 9], 10) == (0, 4)   # 1 + 9 আগে পাওয়া যায়
    assert pair_sum_sorted([1, 3, 4, 6, 9], 7) == (0, 3)    # 1 + 6
    assert pair_sum_sorted([1, 3, 4, 6, 9], 100) is None

    assert longest_unique_substring("abcabcbb") == 3
    assert longest_unique_substring("bbbbb") == 1
    assert longest_unique_substring("") == 0

    p = build_prefix([3, 1, 4, 1, 5])
    assert p == [0, 3, 4, 8, 9, 14]
    assert range_sum(p, 1, 3) == 6      # 1 + 4 + 1
    assert range_sum(p, 0, 4) == 14

    assert count_subarrays_with_sum([1, 2, 1], 3) == 2
    assert count_subarrays_with_sum([1, 1, 1], 2) == 2

    assert is_anagram("listen", "silent") is True
    assert is_anagram("hello", "world") is False
    assert is_anagram("ab", "abc") is False

    assert run_length_encode("aaabb") == "a3b2"
    assert run_length_encode("") == ""
    assert run_length_encode("z") == "z1"

    assert max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
    assert max_subarray_sum([-3, -1, -2]) == -1   # সব negative: best হলো single
    assert max_subarray_sum([5]) == 5

    print("All asserts passed. Arrays and strings: understood by building.")