Hashing & Strings: Deriving the Optimal Solution for 5 Problems (LC 242/49/271/560/128)

Hashing (hash map / hash set) is the most common tool in interviews, and the core is always one line: turn an O(n) lookup/comparison into O(1). The hard part isn't "use a map" — it's figuring out what to use as the key.

This post strings together the main uses of hashing across 5 problems, continuing the full derivation flow from the previous post:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• Counting (242) → using the count as a grouping key (49) → string encoding design (271) → prefix sum + hashing (560) → hash set + boundary expansion (128)

① LC 242 — Valid Anagram

📋 Problem: Given two strings s and t, return whether t is an anagram of s — i.e. each character appears the same number of times in both.

Example: s = "anagram", t = "nagaram" → true; s = "rat", t = "car" → false

🧭 From reading the problem to the solution

1. Break it down: anagram ⟺ identical "char → count" maps.
2. First instinct: sort both strings and compare, O(n log n). Works, but doesn't use hashing.
3. Key insight: instead of sorting, count each character — +1 for s, -1 for t; if everything ends at 0, it's an anagram.
4. Optimum: different lengths → false; otherwise one pass over a count array.

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

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;
}

• Complexity: O(n) time, O(1) space (fixed 26 letters) or O(charset).
• Pitfall: check length first; for Unicode / non-lowercase input, use a HashMap, not a 26-slot array.

② LC 49 — Group Anagrams

📋 Problem: Given an array of strings strs, group the ones that are anagrams of each other, and return all groups.

Example: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]

🧭 From reading the problem to the solution

1. Break it down: "grouping" always implies some shared identifier within a group.
2. From 242: 242 told us anagram ⟺ same character counts. So all anagrams in a group share the same "character count" — that's a natural grouping key!
3. Key insight: compute a canonical key for each string (the sorted string, or the "count of 26 letters") and bucket strings with the same key together.
4. Optimum: a HashMap with key = canonical form, value = the list of strings in that group.

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)   # char-count as key
    return list(groups.values())

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (auto& s : strs) {
        string key = s;
        sort(key.begin(), key.end());    // sorted string as key
        groups[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [k, v] : groups) res.push_back(v);
    return res;
}

• Complexity: O(n·k log k) using a sorted key; O(n·k) using a char-count key (n strings, k average length).
• Pitfall: the key choice drives efficiency — a count key beats a sorted key, but mind hashability (Python tuple, or stringify the counts in C++).

③ LC 271 — Encode and Decode Strings

📋 Problem: Design two functions: encode serializes a list of strings into a single string, and decode restores the original list. Strings may contain any character (including whatever you'd use as a delimiter).

Example: ["lint","code","love you"] → encode to one string → decode back to ["lint","code","love you"]

🧭 From reading the problem to the solution

1. Break it down: this is a design problem — the crux is "how to serialize so it can be unambiguously restored."
2. The wrong instinct: split by a comma or some symbol ("lint,code,..."). Problem: a string might itself contain that comma, so splitting breaks. No single character can safely be a delimiter.
3. Key insight: use length-prefix encoding — prefix each string with its length plus a marker, e.g. 4#lint4#code8#love you. To decode, read the length first, then grab exactly that many characters — regardless of what characters the content contains.
4. Optimum: encode by concatenating len(s) + "#" + s; decode by reading up to #, taking the length, then slicing that many characters.

def encode(strs):
    return ''.join(f'{len(s)}#{s}' for s in strs)

def decode(s):
    res, i = [], 0
    while i < len(s):
        j = i
        while s[j] != '#':            # read the length digits
            j += 1
        length = int(s[i:j])
        res.append(s[j + 1: j + 1 + length])
        i = j + 1 + length
    return res

string encode(vector<string>& strs) {
    string res;
    for (auto& s : strs) res += to_string(s.size()) + "#" + s;
    return res;
}

vector<string> decode(string s) {
    vector<string> res;
    int i = 0, n = s.size();
    while (i < n) {
        int j = i;
        while (s[j] != '#') j++;       // read the length digits
        int len = stoi(s.substr(i, j - i));
        res.push_back(s.substr(j + 1, len));
        i = j + 1 + len;
    }
    return res;
}

• Complexity: O(total length) time and space.
• Pitfall: use "length + marker", not a bare delimiter. A # inside the content is fine — we grab by length, not by searching for the delimiter.

④ LC 560 — Subarray Sum Equals K

📋 Problem: Given an integer array nums and integer k, return the number of contiguous subarrays whose sum is exactly k.

Example: nums = [1,1,1], k = 2 → 2 (two [1,1]); nums = [1,2,3], k = 3 → 2 ([1,2] and [3])

🧭 From reading the problem to the solution

1. Break it down: contiguous subarrays, count those summing to k.
2. Brute force: enumerate every (i, j) and sum, O(n²).
3. Tempted by sliding window? No: nums may contain negatives, so window sums aren't monotonic and sliding window fails. Switch tools.
4. Key insight (prefix sum + hashing): let prefix[j] be the sum of the first j elements; then the sum of range (i, j] = prefix[j] - prefix[i]. For that to equal k ⟺ prefix[i] = prefix[j] - k. So as you scan, ask: "how many earlier prefixes equal prefix - k?" — keep a HashMap of "count of each prefix sum seen".
5. Optimum: accumulate the prefix sum, add count[prefix - k] to the answer, then record the current prefix.

from collections import defaultdict

def subarraySum(nums, k):
    count = defaultdict(int)
    count[0] = 1                  # empty prefix: enables subarrays from index 0
    prefix = res = 0
    for n in nums:
        prefix += n
        res += count[prefix - k]  # how many earlier prefixes = prefix - k
        count[prefix] += 1
    return res

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    count[0] = 1;                 // empty prefix
    int prefix = 0, res = 0;
    for (int n : nums) {
        prefix += n;
        auto it = count.find(prefix - k);
        if (it != count.end()) res += it->second;
        count[prefix]++;
    }
    return res;
}

• Complexity: O(n) time, O(n) space.
• Pitfall: ① count[0] = 1 is essential (so subarrays starting at index 0 are counted); ② add to the answer using count BEFORE recording the current prefix — order matters; ③ with negatives, this is the right approach — don't use a sliding window.

⑤ LC 128 — Longest Consecutive Sequence

📋 Problem: Given an unsorted integer array nums, find the length of the longest consecutive-integers sequence, in O(n) time.

Example: nums = [100,4,200,1,3,2] → 4 (the sequence 1,2,3,4)

🧭 From reading the problem to the solution

1. Break it down: find the longest run of consecutive values (by value, not position), constrained to O(n).
2. Sorting solution: sort then scan, O(n log n) — but the problem demands O(n), so sorting is out.
3. Key insight: put everything in a HashSet (O(1) membership). For each number, only start counting when it's the start of a sequence (i.e. n - 1 is not in the set), then walk up n+1, n+2, .... Each number is visited at most twice.
4. Optimum: iterate the set; at each start, expand to measure the length, and keep the max.

def longestConsecutive(nums):
    num_set = set(nums)
    longest = 0
    for n in num_set:
        if n - 1 not in num_set:        # n is the start of a sequence
            length = 1
            while n + length in num_set:
                length += 1
            longest = max(longest, length)
    return longest

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int longest = 0;
    for (int n : s) {
        if (s.find(n - 1) == s.end()) {     // n is a sequence start
            int length = 1;
            while (s.find(n + length) != s.end()) length++;
            longest = max(longest, length);
        }
    }
    return longest;
}

• Complexity: O(n) time, O(n) space.
• Pitfall: "only expand from a start" (n-1 not in the set) is what keeps it O(n) — without that check you'd re-walk the same sequence repeatedly and degrade to O(n²).

One Table to Remember It All

Pattern-Recognition Cheats

• "anagram / character counts" → a count table.
• "group / categorize" → ask "what key do members of a group share?"
• "serialize strings that may contain any character" → length-prefix encoding, not a delimiter.
• "contiguous subarray summing to k" with possible negatives → prefix sum + hashing (not sliding window).
• "longest consecutive, in O(n)" → HashSet + expand only from starts.

The essence of hashing problems isn't "use a map" — it's choosing the right key: a count, a prefix sum, a canonical string. Nail the key and the problem is half solved.