Array and String Manipulation Questions

# build SA (doubling with radix sort), build LCP (Kasai)
distinct = sum((n - SA[i]) - LCP[i] for i in range(n))

// Returns true if s1 and s2 are anagrams (Unicode-aware, case-insensitive)
function areAnagrams(s1, s2) {
  // Normalize and case-fold (toLowerCase is best available in JS; consider locale if needed)
  const a = s1.normalize('NFC').toLowerCase();
  const b = s2.normalize('NFC').toLowerCase();

  // Quick length check in code points (iterate to count without creating arrays)
  let lenA = 0, lenB = 0;
  for (const _ of a) lenA++;
  for (const _ of b) lenB++;
  if (lenA !== lenB) return false;

  // Build frequency map for a, decrement with b
  const freq = new Map();
  for (const ch of a) freq.set(ch, (freq.get(ch) || 0) + 1);
  for (const ch of b) {
    const c = freq.get(ch);
    if (!c) return false;
    if (c === 1) freq.delete(ch); else freq.set(ch, c - 1);
  }
  return freq.size === 0;
}

from collections import Counter
import heapq

def reorganize_string(s: str) -> str:
    # Count frequencies
    counts = Counter(s)
    # Max-heap in Python using negative counts
    heap = [(-cnt, ch) for ch, cnt in counts.items()]
    heapq.heapify(heap)
    res = []

    # Greedy: always take top two different chars
    while len(heap) >= 2:
        cnt1, ch1 = heapq.heappop(heap)
        cnt2, ch2 = heapq.heappop(heap)
        res.extend([ch1, ch2])
        # decrement and push back if still available
        if cnt1 + 1 < 0:
            heapq.heappush(heap, (cnt1 + 1, ch1))
        if cnt2 + 1 < 0:
            heapq.heappush(heap, (cnt2 + 1, ch2))

    # If one remains, it can be placed only if count == 1
    if heap:
        cnt, ch = heapq.heappop(heap)
        if cnt == -1:
            res.append(ch)
        else:
            return ""  # impossible

    return "".join(res)

// Returns "IPv4", "IPv6" or "Neither"
function validateIP(s) {
  if (s.includes('.')) return isIPv4(s) ? "IPv4" : "Neither";
  if (s.includes(':')) return isIPv6(s) ? "IPv6" : "Neither";
  return "Neither";
}

function isIPv4(s) {
  const parts = s.split('.');
  if (parts.length !== 4) return false;
  for (const p of parts) {
    if (p.length === 0) return false;
    if (p[0] === '0' && p.length > 1) return false; // leading zero
    if (!/^\d+$/.test(p)) return false;
    const n = Number(p);
    if (n < 0 || n > 255) return false;
  }
  return true;
}

function isIPv6(s) {
  if (s === '::') return true;
  const parts = s.split('::');
  if (parts.length > 2) return false; // more than one '::'
  const left = parts[0] ? parts[0].split(':').filter(Boolean) : [];
  const right = parts[1] ? parts[1].split(':').filter(Boolean) : [];
  if (left.length + right.length > 8) return false;
  const groups = [...left, ...right];
  if (groups.length === 0) return false;
  for (const g of groups) {
    if (!/^[0-9a-fA-F]{1,4}$/.test(g)) return false;
  }
  return left.length + right.length <= 8;
}

def reverse_words(s: str) -> str:
    # split() trims and collapses multiple spaces by default
    words = s.split()
    # reverse list and join with single space
    return " ".join(reversed(words))

# Example:
# reverse_words("  the   sky is  blue ") -> "blue is sky the"