string cp questions

Table of Contents

1. Anagram Pattern Matching
2. Anagram Check
3. Concatenate Strings with Common Substrings
4. Compare Strings After Processing Backspaces
5. Word Frequency Count
6. Longest Substring with Limited Replacements
7. Reverse Words in a String
8. Reverse Characters in Each Word
9. Longest Substring with K Unique Characters
10. Longest Substring Without Repeating Characters
11. Count Unique Characters

---

Anagram Pattern Matching

Function: findAnagramPattern()

Description: Finds the starting index of the first substring in s1 that is an anagram of s2.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void findAnagramPattern(string s1, string s2) {
        int n = s1.size();
        int m = s2.size();
        int start = 0;
        int end = m;

        while (end <= n) {
            string temp = s1.substr(start, end - start);
            cout << temp << ">" << endl;
            sort(temp.begin(), temp.end());
            sort(s2.begin(), s2.end());

            if (temp == s2) {
                cout << start << " ";
                break;
            }

            start++;
            end++;
        }
    }
};

int main() {
    Solution ob;
    string s1 = "abbcdffhabc";
    string s2 = "abc";
    ob.findAnagramPattern(s1, s2);
}

Explanation:

• Purpose: Identify if there is a substring in s1 which is an anagram of s2.
• Approach: Slide a window of size m (length of s2) across s1, sort the substring and compare it with the sorted s2.

---

Anagram Check

Function: areAnagrams()

Description: Checks if two strings are anagrams of each other.

Code:

#include<bits/stdc++.h>
using namespace std;

class Anagram {
public:
    bool areAnagrams(string s1, string s2) {
        int len = s1.size();
        if (len != s2.size()) return false;

        unordered_map<char, int> charCount;
        for (int i = 0; i < len; i++) {
            charCount[s1[i]]++;
            charCount[s2[i]]--;
        }

        for (auto i : charCount) {
            if (i.second != 0) return false;
        }

        return true;
    }
};

int main() {
    Anagram ob;
    cout << ob.areAnagrams("CAT", "ACT");
}

Explanation:

• Purpose: Determine if two strings are anagrams.
• Approach: Use a frequency map to count characters in both strings and compare.

---

Concatenate Strings with Common Substrings

Function: concatenateWithCommonSubstring()

Description: Concatenates s1 and s2 by finding the longest common suffix of s1 and prefix of s2.

Code:

#include<bits/stdc++.h>
using namespace std;

int main() {
    string s1 = "ahello";
    string s2 = "lolo";
    int l1 = s1.length(), l2 = s2.length();
    int len = min(l1, l2);
    int overlap = 0;

    for (int i = 1; i < len; i++) {
        cout << s1.substr(l1 - i, i) << ":" << s2.substr(0, i) << endl;
        if (s1.substr(l1 - i, i) == s2.substr(0, i)) overlap = i;
    }

    cout << s1 + s2.substr(overlap);
}

Explanation:

• Purpose: Concatenate s1 and s2 with maximum overlap.
• Approach: Find the longest suffix of s1 that matches the prefix of s2 and concatenate accordingly.

---

Compare Strings After Processing Backspaces

Function: compareStringsAfterBackspace()

Description: Compares two strings after removing characters represented by backspace (#).

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool compareStringsAfterBackspace(string s1, string s2) {
        processBackspaces(s1);
        processBackspaces(s2);
        return s1 == s2;
    }

    void processBackspaces(string &s) {
        int i = 0;
        while (i < s.size()) {
            if (s[i] == '#') {
                if (i > 0) {
                    s.erase(i - 1, 1);
                    i--;
                }
                s.erase(i, 1);
            } else {
                i++;
            }
        }
    }
};

int main() {
    Solution ob;
    string s1 = "abb#c";
    string s2 = "ad#c";
    ob.processBackspaces(s1);
    ob.processBackspaces(s2);
    cout << s1 << endl;
    cout << s2 << endl;
    cout << ob.compareStringsAfterBackspace(s1, s2);
}

Explanation:

• Purpose: Compare two strings after simulating backspace operations.
• Approach: Process each string to remove characters as indicated by # and then compare.

---

Word Frequency Count

Function: countWordFrequency()

Description: Counts and prints the frequency of each word in a string.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void countWordFrequency(string s) {
        unordered_map<string, int> wordCount;
        string temp = "";
        
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                wordCount[temp]++;
                temp.clear();
            } else {
                temp += s[i];
            }
        }
        wordCount[temp]++;
        
        for (auto x : wordCount) {
            cout << x.first << ":" << x.second << endl;
        }
    }
};

int main() {
    Solution ob;
    string s = "I am a good lol animal I am a good animal";
    ob.countWordFrequency(s);
}

Explanation:

• Purpose: Count and display the frequency of each word in a given string.
• Approach: Use a hash map to count occurrences of each word separated by spaces.

---

Longest Substring with Limited Replacements

Function: longestSubstringWithLimitedReplacements()

Description: Finds the length of the longest substring where you can replace up to k characters to make all characters in the substring the same.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void longestSubstringWithLimitedReplacements(string s, int k) {
        int start, end;
        start = end = 0;
        int maxLen = 0;
        int maxFreq = 0;
        unordered_map<char, int> charCount;
        
        while (end < s.size()) {
            charCount[s[end]]++;
            maxFreq = max(maxFreq, charCount[s[end]]);
            
            if (end - start + 1 - maxFreq > k) {
                charCount[s[start]]--;
                start++;
            }
            
            maxLen = max(maxLen, end - start + 1);
            end++;
        }
        
        cout << maxLen << endl;
    }
};

int main() {
    Solution s;
    string str;
    int k;
    cin >> str >> k;
    s.longestSubstringWithLimitedReplacements(str, k);
    return 0;
}

Explanation:

• Purpose: Find the longest substring where you can replace up to k characters to achieve a uniform substring.
• Approach: Use a sliding window with a frequency map to keep track of character counts and adjust the window size based on allowed replacements.

---

Reverse Words in a String

Function: reverseWordsInString()

Description: Reverses the order of words in a string while keeping the words themselves intact.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void reverseWordsInString(string s) {
        string result = "";
        string word = "";
        
        for (char c : s) {
            if (c != ' ') {
                word.push_back(c);
            } else {
                result = word + ' ' + result;
                word.clear();
            }
        }
        result = word + ' ' + result;
        cout << result;
    }
};

int main() {
    Solution ob;
    ob.reverseWordsInString("hello world allu kaju katli");
}

Explanation:

• Purpose: Reverse the order of words in a string.
• Approach: Traverse the string, build words, and prepend them to the result.

---

Reverse Characters in Each Word

Function: reverseCharactersInWords()

Description: Reverses the characters of each word in the given string while keeping the word order intact.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void reverseCharactersInWords(string s) {
        string result = "";
        string word = "";
        
        for (char c : s) {
            if (c != ' ') {
                word = c + word;
            } else {
                result += word + ' ';
                word.clear();
            }
        }
        result += word;
        cout << result;
    }
};

int main() {
    Solution ob;
    ob.reverseCharactersInWords("hello world");
}

Explanation:

• Purpose: Reverse the characters of each individual word in a string.
• Approach: Build each word in reverse order and append to the result.

---

Longest Substring with K Unique Characters

Function: longestSubstringWithKUniqueChars()

Description: Finds the length of the longest substring with exactly k unique characters.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void longestSubstringWithKUniqueChars(string s, int k) {
        int n = s.size();
        int start, end;
        start = end = 0;
        unordered_map<char, int> charCount;
        int max_len = 0;

        while (end < n) {
            charCount[s[end]]++;
            while (charCount.size() > k) {
                charCount[s[start]]--;
                if (charCount[s[start]] == 0) {
                    charCount.erase(s[start]);
                }
                start++;
            }
            max_len = max(max_len, end - start + 1);
            end++;
        }
        
        cout << max_len;
    }
};

int main() {
    Solution ob;
    ob.longestSubstringWithKUniqueChars("abcabcbb", 2);
}

Explanation:

• Purpose: Find the length of the longest substring containing exactly k unique characters.
• Approach: Use a sliding window and a frequency map to manage unique characters.

---

Longest Substring Without Repeating Characters

Function: longestSubstringWithoutRepeatingChars()

Description: Finds the length of the longest substring without repeating characters.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    void longestSubstringWithoutRepeatingChars(string s) {
        int start, end;
        start = end = 0;
        unordered_map<char, int> charIndex;
        int max_len = 0;

        while (end < s.size()) {
            if (charIndex.find(s[end]) == charIndex.end()) {
                charIndex[s[end]] = end;
            } else {
                start = max(start, charIndex[s[end]] + 1);
                charIndex[s[end]] = end;
            }
            max_len = max(max_len, end - start + 1);
            end++;
        }
        
        cout << max_len;
    }
};

int main() {
    Solution ob;
    ob.longestSubstringWithoutRepeatingChars("abcabcbb");
}

Explanation:

• Purpose: Find the length of the longest substring without repeating characters.
• Approach: Use a sliding window with a map to keep track of the last index of each character.

---

Count Unique Characters

Function: countUniqueCharacters()

Description: Counts and prints the number of unique characters in a string.

Code:

#include<bits/stdc++.h>
using namespace std;

class Solution {
private:
    unordered_set<char> uniqueChars;
public:
    void countUniqueCharacters(string s) {
        for (char c : s) {
            uniqueChars.insert(c);
        }
        cout << uniqueChars.size();
    }
};

int main() {
    Solution ob;
    ob.countUniqueCharacters("ababababa");
}

Explanation:

• Purpose: Count the number of unique characters in a string.
• Approach: Use an unordered set to collect unique characters and count them.