Trpaping Rain Water Problem

Given an array representing elevation maps, this problem calculates how much water can be trapped between bars after raining.

vector<int> leftMax(n, 0);
vector<int> rightMax(n, 0);
if (n == 0) return 0;
leftMax[0] = height[0];
rightMax[n-1] = height[n-1];

for (int i = 1; i < n; ++i) {
    leftMax[i] = max(leftMax[i-1], height[i]);
}
for (int i = height.size() - 2; i >= 0; --i) {
    rightMax[i] = max(rightMax[i+1], height[i]);
}

int ans = 0;
for (int i = 0; i < n; ++i) {
    ans += min(leftMax[i], rightMax[i]) - height[i];
}
return ans;

Longest Substring Without Repeating Characters

This sliding window problem requires finding the longest substring with all unique characters.

int lengthOfLongestSubstring(string s) {
    int right = -1;
    int maxSub = 0;
    int n = s.length();
    unordered_set<char> result;
    
    for (int i = 0; i < n; ++i) {
        if (i != 0) result.erase(s[i-1]);
        while (right + 1 < n && !result.count(s[right+1])) {
            result.insert(s[right+1]);
            right++;
        }
        maxSub = max(maxSub, right - i + 1);
    }
    return maxSub;
}

Key Insights from This Problem

The sliding window technique demonstrates several important concepts:

• Data Structure Selection: Using unordered_set efficiently tracks unique characters within the current window
• Window Manipulation: The right pointer expands continuously while the left pointer removes characters when sliding
• Set Operations:
  • set.erase(element): removes element from set
  • set.insert(element): adds element to set
  • set.count(element): returns 0 if absent, 1 if present

Find All Anagrams in a String

This problem combines hash tables with sliding window technique to find all starting positions where p's anagram appears in s.

vector<int> findAnagrams(string s, string p) {
    int sLen = s.size();
    int pLen = p.size();
    if (sLen < pLen) return vector<int>();
    
    vector<int> ans;
    vector<int> sCount(26);
    vector<int> pCount(26);
    
    for (int i = 0; i < pLen; ++i) {
        ++sCount[s[i] - 'a'];
        ++pCount[p[i] - 'a'];
    }
    
    // Compare vectors directly to check for anagrams
    // Slide window and update counts as needed
    for (int i = 0; i < sLen - pLen + 1; ++i) {
        if (sCount == pCount) {
            ans.push_back(i);
        }
        // Update sliding window
        --sCount[s[i] - 'a'];
        if (i + pLen < sLen) {
            ++sCount[s[i + pLen] - 'a'];
        }
    }
    return ans;
}

Valuable Techniques Demonstrated

• Direct vector comparison for checking anagram equivalence
• Efficient sliding window updates using character frequency counts
• Character-to-index mapping using ASCII offset

Common Pitfalls and Lessons Learned

1. Incomplete Problem Analysis: Initial solutions may overlook edge cases like overlapping patterns (e.g., "abcabc" contains repeated segments)
2. Data Structure Awareness: Not recognizing opportunities to use structures like unordered_set, unordered_map, or stacks for solving problems
3. Boundary Conditions: Understanding the relationship between window boundaries, particularly how the right pointer relates to the current index in sliding window implementations
4. Algorithm Verificatino: Thorough testing against various input patterns helps identify logical errors early