DSA Sheet - Day 7 Strings

🚀 DSA Sheet – Day 7: Strings (Part 2)

This section dives into advanced string algorithms and pattern matching techniques like KMP and Rabin-Karp. These are high-impact topics frequently asked in top interviews.

📊 Progress Tracker

Progress: 0 / 6 Completed

Done	Problem	Practice	Level	Companies
	Longest Common Prefix	Solve	Easy	Meta, Microsoft, Amazon
	Group Anagrams	Solve	Medium	Nvidia, TCS, Salesforce
	Minimum Window Substring	Solve	Hard	Amazon, Google
	KMP Algorithm	Learn	Hard	Amazon, Google
	Rabin-Karp Algorithm	Learn	Hard	Microsoft
	Reverse Words in String	Solve	Medium	Amazon

🧠 Key Approaches

• Longest Common Prefix: Compare characters across all strings
• Group Anagrams: Sort string OR use frequency map as key
• Minimum Window Substring: Sliding window + hashmap
• KMP Algorithm: Preprocess pattern using LPS array
• Rabin-Karp: Rolling hash for efficient matching
• Reverse Words: Trim + reverse logic

⚡ Quick Cheatsheet

Group Anagrams

unordered_map> mp;

for(string s : strs){
  string t = s;
  sort(t.begin(), t.end());
  mp[t].push_back(s);
}
    

Minimum Window Substring

unordered_map mp;

for(char c : t) mp[c]++;

int count = t.size();
int l = 0;

for(int r = 0; r < s.size(); r++){
  if(mp[s[r]]-- > 0) count--;

  while(count == 0){
    // update answer here

    if(mp[s[l++]]++ == 0) 
      count++;
  }
}
    

KMP Algorithm (LPS Array)

vector lps(n);

for(int i = 1, len = 0; i < n; ){
  if(p[i] == p[len]) 
    lps[i++] = ++len;
  else if(len) 
    len = lps[len - 1];
  else 
    lps[i++] = 0;
}
    

🔥 Pro Tip

Advanced string problems are all about pattern recognition:

• Sliding Window Optimization
• Pattern Matching (KMP, Rabin-Karp)
• Hashing Techniques

Once you understand these, even hard problems become manageable.

🏠 All Days ⬅ Previous Next ➡