Practice Problems

function isPalindrome(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        while (left < right && !/[a-zA-Z0-9]/.test(s[left])) left++;
        while (left < right && !/[a-zA-Z0-9]/.test(s[right])) right--;
        if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
        left++;
        right--;
    }
    return true;
}

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        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, right = left + 1, right - 1
    return True

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
            left++;
            right--;
        }
        return true;
    }
}

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) left++;
            while (left < right && !isalnum(s[right])) right--;
            if (tolower(s[left++]) != tolower(s[right--])) return false;
        }
        return true;
    }
};

func isPalindrome(s string) bool {
    s = strings.ToLower(s)
    left, right := 0, len(s)-1
    for left < right {
        for left < right && !isAlnum(s[left]) {
            left++
        }
        for left < right && !isAlnum(s[right]) {
            right--
        }
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

func isAlnum(b byte) bool {
    return (b >= 'a' && b <= 'z') || (b >= '0' && b <= '9')
}

def is_palindrome(s)
  s = s.downcase.gsub(/[^a-z0-9]/, '')
  s == s.reverse
end

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    const count = {};
    for (let char of s) count[char] = (count[char] || 0) + 1;
    for (let char of t) {
        if (!count[char]) return false;
        count[char]--;
    }
    return true;
}

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t): return False
    count = {}
    for char in s: count[char] = count.get(char, 0) + 1
    for char in t:
        if char not in count or count[char] == 0: return False
        count[char] -= 1
    return True

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }
}

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;
        int count[26] = {0};
        for (char c : s) count[c - 'a']++;
        for (char c : t) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }
};

func isAnagram(s string, t string) bool {
    if len(s) != len(t) { return false }
    count := make(map[rune]int)
    for _, r := range s { count[r]++ }
    for _, r := range t {
        if count[r] == 0 { return false }
        count[r]--
    }
    return true
}

def is_anagram(s, t)
  return false if s.length != t.length
  count = Hash.new(0)
  s.each_char { |c| count[c] += 1 }
  t.each_char { |c|
    return false if count[c] == 0
    count[c] -= 1
  }
  true
end

function lengthOfLongestSubstring(s) {
    let set = new Set();
    let left = 0, right = 0, maxLen = 0;
    while (right < s.length) {
        while (set.has(s[right])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
        right++;
    }
    return maxLen;
}

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, max = 0;
        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.size(); right++) {
            while (charSet.count(s[right])) {
                charSet.erase(s[left++]);
            }
            charSet.insert(s[right]);
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

func lengthOfLongestSubstring(s string) int {
    charMap := make(map[byte]bool)
    left, maxLen := 0, 0
    for right := 0; right < len(s); right++ {
        for charMap[s[right]] {
            delete(charMap, s[left])
            left++
        }
        charMap[s[right]] = true
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
    return maxLen
}

def length_of_longest_substring(s)
  char_set = Set.new
  left = 0
  max_len = 0
  s.each_char.with_index do |char, right|
    while char_set.include?(char)
      char_set.delete(s[left])
      left += 1
    end
    char_set.add(char)
    max_len = [max_len, right - left + 1].max
  end
  max_len
end

function minWindow(s, t) {
    let need = {}, window = {};
    for (let c of t) need[c] = (need[c] || 0) + 1;
    let left = 0, right = 0, valid = 0;
    let start = 0, len = Infinity;
    while (right < s.length) {
        let c = s[right++];
        if (need[c]) {
            window[c] = (window[c] || 0) + 1;
            if (window[c] === need[c]) valid++;
        }
        while (valid === Object.keys(need).length) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            let d = s[left++];
            if (need[d]) {
                if (window[d] === need[d]) valid--;
                window[d]--;
            }
        }
    }
    return len === Infinity ? "" : s.substr(start, len);
}

def minWindow(s: str, t: str) -> str:
    from collections import Counter
    need = Counter(t)
    window = Counter()
    left = right = 0
    valid = 0
    start, length = 0, float('inf')
    while right < len(s):
        c = s[right]
        right += 1
        if c in need:
            window[c] += 1
            if window[c] == need[c]:
                valid += 1
        while valid == len(need):
            if right - left < length:
                start = left
                length = right - left
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    return "" if length == float('inf') else s[start:start + length]

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
        int left = 0, right = 0, valid = 0, start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++;
            }
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        int left = 0, right = 0, valid = 0, start = 0, len = INT_MAX;
        while (right < s.size()) {
            char c = s[right++];
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) valid++;
            }
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s[left++];
                if (need.count(d)) {
                    if (window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

func minWindow(s string, t string) string {
    need, window := make(map[byte]int), make(map[byte]int)
    for i := 0; i < len(t); i++ { need[t[i]]++ }
    left, right, valid, start, length := 0, 0, 0, 0, math.MaxInt32
    for right < len(s) {
        c := s[right]
        right++
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] { valid++ }
        }
        for valid == len(need) {
            if right-left < length {
                start = left
                length = right - left
            }
            d := s[left]
            left++
            if _, ok := need[d]; ok {
                if window[d] == need[d] { valid-- }
                window[d]--
            }
        }
    }
    if length == math.MaxInt32 { return "" }
    return s[start : start+length]
}

def min_window(s, t)
  need = Hash.new(0)
  t.each_char { |c| need[c] += 1 }
  window = Hash.new(0)
  left = right = valid = start = 0
  len = Float::INFINITY
  while right < s.length
    c = s[right]
    right += 1
    if need.key?(c)
      window[c] += 1
      valid += 1 if window[c] == need[c]
    end
    while valid == need.size
      if right - left < len
        start = left
        len = right - left
      end
      d = s[left]
      left += 1
      if need.key?(d)
        valid -= 1 if window[d] == need[d]
        window[d] -= 1
      end
    end
  end
  len == Float::INFINITY ? "" : s[start, len]
end

function groupAnagrams(strs) {
    const map = new Map();
    for (let s of strs) {
        let sorted = s.split('').sort().join('');
        if (!map.has(sorted)) map.set(sorted, []);
        map.get(sorted).push(s);
    }
    return Array.from(map.values());
}

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = {}
    for s in strs:
        sorted_s = "".join(sorted(s))
        if sorted_s not in groups: groups[sorted_s] = []
        groups[sorted_s].append(s)
    return list(groups.values())

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String sorted = new String(chars);
            if (!map.containsKey(sorted)) map.put(sorted, new ArrayList<>());
            map.get(sorted).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (string& s : strs) {
            string sorted = s;
            sort(sorted.begin(), sorted.end());
            groups[sorted].push_back(s);
        }
        vector<vector<string>> result;
        for (auto& entry : groups) result.push_back(entry.second);
        return result;
    }
};

func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, s := range strs {
        chars := strings.Split(s, "")
        sort.Strings(chars)
        sorted := strings.Join(chars, "")
        groups[sorted] = append(groups[sorted], s)
    }
    result := [][]string{}
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

def group_anagrams(strs)
  groups = Hash.new { |h, k| h[k] = [] }
  strs.each do |s|
    sorted_s = s.chars.sort.join
    groups[sorted_s] << s
  end
  groups.values
end

function longestDupSubstring(s) {
    let n = s.length;
    let base = 26n, mod = 2n**63n - 1n;
    let left = 1, right = n - 1;
    let res = "";

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let found = check(mid);
        if (found !== null) {
            res = s.substring(found, found + mid);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    function check(len) {
        let h = 0n;
        for (let i = 0; i < len; i++) h = (h * base + BigInt(s.charCodeAt(i) - 97)) % mod;
        let seen = new Set([h]);
        let aL = 1n;
        for (let i = 0; i < len; i++) aL = (aL * base) % mod;

        for (let i = 1; i <= n - len; i++) {
            h = (h * base - BigInt(s.charCodeAt(i - 1) - 97) * aL % mod + mod) % mod;
            h = (h + BigInt(s.charCodeAt(i + len - 1) - 97)) % mod;
            if (seen.has(h)) return i;
            seen.add(h);
        }
        return null;
    }
    return res;
}

def longestDupSubstring(s: str) -> str:
    n = len(s)
    nums = [ord(c) - ord('a') for c in s]
    base = 26
    mod = 2**63 - 1

    def check(length):
        h = 0
        for i in range(length):
            h = (h * base + nums[i]) % mod
        seen = {h}
        aL = pow(base, length, mod)
        for i in range(1, n - length + 1):
            h = (h * base - nums[i - 1] * aL % mod + mod) % mod
            h = (h + nums[i + length - 1]) % mod
            if h in seen: return i
            seen.add(h)
        return -1

    left, right = 1, n - 1
    start, max_len = 0, 0
    while left <= right:
        mid = (left + right) // 2
        pos = check(mid)
        if pos != -1:
            start, max_len = pos, mid
            left = mid + 1
        else:
            right = mid - 1
    return s[start:start + max_len]

class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = s.charAt(i) - 'a';
        long mod = (1L << 61) - 1;
        int left = 1, right = n - 1;
        int start = 0, maxLen = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int pos = check(mid, n, nums, mod);
            if (pos != -1) {
                start = pos;
                maxLen = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int check(int len, int n, int[] nums, long mod) {
        long h = 0, aL = 1, base = 26;
        for (int i = 0; i < len; i++) {
            h = (h * base + nums[i]) % mod;
            aL = (aL * base) % mod;
        }
        Set<Long> seen = new HashSet<>();
        seen.add(h);
        for (int i = 1; i <= n - len; i++) {
            h = (h * base - nums[i - 1] * aL % mod + mod) % mod;
            h = (h + nums[i + len - 1]) % mod;
            if (seen.contains(h)) return i;
            seen.add(h);
        }
        return -1;
    }
}

class Solution {
public:
    string longestDupSubstring(string s) {
        int n = s.size();
        vector<int> nums(n);
        for (int i = 0; i < n; i++) nums[i] = s[i] - 'a';
        long long mod = (1ULL << 61) - 1;
        int left = 1, right = n - 1, start = 0, maxLen = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int pos = check(mid, n, nums, mod);
            if (pos != -1) {
                start = pos;
                maxLen = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return s.substr(start, maxLen);
    }

    int check(int len, int n, vector<int>& nums, long long mod) {
        __int128 h = 0, aL = 1, base = 26;
        for (int i = 0; i < len; i++) {
            h = (h * base + nums[i]) % mod;
            aL = (aL * base) % mod;
        }
        unordered_set<long long> seen;
        seen.insert((long long)h);
        for (int i = 1; i <= n - len; i++) {
            h = (h * base - nums[i - 1] * aL % mod + mod) % mod;
            h = (h + nums[i + len - 1]) % mod;
            if (seen.count((long long)h)) return i;
            seen.insert((long long)h);
        }
        return -1;
    }
};

func longestDupSubstring(s string) string {
    n := len(s)
    nums := make([]int, n)
    for i := 0; i < n; i++ { nums[i] = int(s[i] - 'a') }
    mod := uint64(1<<61 - 1)
    left, right := 1, n-1
    resStart, resLen := 0, 0
    for left <= right {
        mid := (left + right) / 2
        pos := check(mid, n, nums, mod)
        if pos != -1 {
            resStart, resLen = pos, mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return s[resStart : resStart+resLen]
}

func check(length, n int, nums []int, mod uint64) int {
    var h, aL, base uint64 = 0, 1, 26
    for i := 0; i < length; i++ {
        h = (h*base + uint64(nums[i])) % mod
        aL = (aL * base) % mod
    }
    seen := map[uint64]struct{}{h: {}}
    for i := 1; i <= n-length; i++ {
        h = (h*base + uint64(nums[i+length-1])) % mod
        h = (h - (uint64(nums[i-1])*aL)%mod + mod) % mod
        if _, ok := seen[h]; ok { return i }
        seen[h] = struct{}{}
    }
    return -1
}

def longest_dup_substring(s)
  n = s.length
  nums = s.chars.map { |c| c.ord - 'a'.ord }
  base = 26
  mod = (1 << 61) - 1

  check = lambda do |length|
    h = 0
    al = 1
    length.times do |i|
      h = (h * base + nums[i]) % mod
      al = (al * base) % mod
    end
    seen = { h => true }
    (1..n - length).each do |i|
      h = (h * base - nums[i - 1] * al % mod + mod) % mod
      h = (h + nums[i + length - 1]) % mod
      return i if seen[h]
      seen[h] = true
    end
    nil
  end

  left, right = 1, n - 1
  res_start, res_len = 0, 0
  while left <= right
    mid = (left + right) / 2
    pos = check.call(mid)
    if pos
      res_start, res_len = pos, mid
      left = mid + 1
    else
      right = mid - 1
    end
  end
  s[res_start, res_len]
end