Arrays và Strings: Nền tảng của Cấu trúc Dữ liệu

// TypeScript - Dynamic array (tự động phát triển)
const arr: number[] = [1, 2, 3];
arr.push(4);  // Thêm vào cuối - thường O(1), đôi khi O(n) khi resize
arr.push(5);

# Python - Lists là dynamic arrays
arr = [1, 2, 3]
arr.append(4)  # O(1) amortized
arr.append(5)

// TypeScript - Two Sum trong Array đã sắp xếp
function twoSumSorted(nums: number[], target: number): number[] {
  let left = 0;
  let right = nums.length - 1;
 
  while (left < right) {
    const sum = nums[left] + nums[right];
 
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;  // Cần tổng lớn hơn
    } else {
      right--; // Cần tổng nhỏ hơn
    }
  }
 
  return [-1, -1]; // Không tìm thấy
}
 
console.log(twoSumSorted([2, 7, 11, 15], 9)); // [0, 1]

# Python - Two Sum trong Array đã sắp xếp
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
 
    while left < right:
        current_sum = nums[left] + nums[right]
 
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
 
    return [-1, -1]

// TypeScript - Xóa Duplicates từ Array đã sắp xếp (in-place)
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
 
  let slow = 0;  // Trỏ đến phần tử unique cuối cùng
 
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
 
  return slow + 1;  // Độ dài phần unique
}

// TypeScript - Tổng lớn nhất của k phần tử liên tiếp
function maxSumSubarray(nums: number[], k: number): number {
  if (nums.length < k) return -1;
 
  // Tính tổng của window đầu tiên
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
 
  let maxSum = windowSum;
 
  // Trượt window
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i];      // Thêm phần tử mới
    windowSum -= nums[i - k];  // Xóa phần tử cũ
    maxSum = Math.max(maxSum, windowSum);
  }
 
  return maxSum;
}
 
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

// TypeScript/JavaScript - Strings là immutable
let s = "hello";
// s[0] = "H";  // Điều này không hoạt động!
s = "H" + s.slice(1);  // Tạo string mới
console.log(s); // "Hello"

# Python - Strings là immutable
s = "hello"
# s[0] = "H"  # TypeError!
s = "H" + s[1:]  # Tạo string mới
 
# Để có thể thay đổi, dùng list rồi join
chars = list("hello")
chars[0] = "H"
s = "".join(chars)
print(s)  # "Hello"

// TypeScript - Two Sum dùng Hash Map - O(n)
function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
 
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
 
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
 
    seen.set(nums[i], i);
  }
 
  return [-1, -1];
}
 
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

# Python - Two Sum dùng Hash Map - O(n)
def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
 
    for i, num in enumerate(nums):
        complement = target - num
 
        if complement in seen:
            return [seen[complement], i]
 
        seen[num] = i
 
    return [-1, -1]

// TypeScript - Thuật toán Kadane - O(n)
function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
 
  for (let i = 1; i < nums.length; i++) {
    // Hoặc mở rộng subarray hiện tại hoặc bắt đầu mới
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
 
  return maxSum;
}
 
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

// TypeScript - Xoay Array - O(n) time, O(1) space
function rotate(nums: number[], k: number): void {
  k = k % nums.length;
 
  // Đảo ngược toàn bộ array
  reverse(nums, 0, nums.length - 1);
  // Đảo ngược k phần tử đầu
  reverse(nums, 0, k - 1);
  // Đảo ngược các phần tử còn lại
  reverse(nums, k, nums.length - 1);
}
 
function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    [nums[start], nums[end]] = [nums[end], nums[start]];
    start++;
    end--;
  }
}
 
const arr = [1, 2, 3, 4, 5, 6, 7];
rotate(arr, 3);
console.log(arr); // [5, 6, 7, 1, 2, 3, 4]

// TypeScript - Valid Palindrome - O(n)
function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
 
  while (left < right) {
    // Bỏ qua non-alphanumeric
    while (left < right && !isAlphanumeric(s[left])) {
      left++;
    }
    while (left < right && !isAlphanumeric(s[right])) {
      right--;
    }
 
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }
 
    left++;
    right--;
  }
 
  return true;
}
 
function isAlphanumeric(char: string): boolean {
  return /[a-zA-Z0-9]/.test(char);
}
 
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true

# Python - Valid Anagram dùng Counter - O(n)
from collections import Counter
 
def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)
 
print(is_anagram("anagram", "nagaram"))  # True
print(is_anagram("rat", "car"))  # False

// TypeScript - Chuỗi con dài nhất không có ký tự lặp
function lengthOfLongestSubstring(s: string): number {
  const charIndex = new Map<string, number>();
  let maxLength = 0;
  let left = 0;
 
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
 
    // Nếu char đã thấy và nằm trong window hiện tại
    if (charIndex.has(char) && charIndex.get(char)! >= left) {
      left = charIndex.get(char)! + 1;  // Thu nhỏ window
    }
 
    charIndex.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }
 
  return maxLength;
}
 
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")