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: Identifies 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: To find if there is a substring in s1 which is an anagram of s2.
• Example:
  • Input: s1 = "abbcdffhabc", s2 = "abc"
  • Process: Slide a window of size 3 (length of s2) across s1, sort both the substring and s2, and compare. When a match is found, print the starting index.
  • Output: The program finds the substring "abc" starting at index 7 which is an anagram of s2.

---

Anagram Check

Function: areAnagrams()

Description: Determines 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: To check if two strings are anagrams by comparing character counts.
• Example:
  • Input: s1 = "CAT", s2 = "ACT"
  • Process: Count the frequency of each character in both strings. If the frequencies match, they are anagrams.
  • Output: 1 (true) indicating that "CAT" and "ACT" are anagrams.

---

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: To concatenate s1 and s2 such that they overlap as much as possible.
• Example:
  • Input: s1 = "ahello", s2 = "lolo"
  • Process: Find the longest suffix of s1 that matches the prefix of s2 and concatenate s1 with the non-overlapping part of s2.
  • Output: "ahellolo"

---

Compare Strings After Processing Backspaces

Function: compareStringsAfterBackspace()

Description: Compares two strings after removing characters indicated by backspaces (#).

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: To compare two strings after simulating the effect of backspace operations.
• Example:
  • Input: s1 = "abb#c", s2 = "ad#c"
  • Process: Remove characters before and after backspaces and then compare the processed strings.
  • Output: 1 (true) indicating that "abc" and "ac" are equal after processing.

---

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: To count how often each word appears in the string.
• Example:
  • Input: s = "I am a good lol animal I am a good animal"
  • Process: Split the string into words and use a map to count each word’s occurrences.
  • Output:

    I:2
    am:2
    a:2
    good:2
    lol:1
    animal:2
    

---

Longest Substring with Limited Replacements

Function: longestSubstringWithLimitedReplacements()

Description: Finds the length of the longest substring where up to k characters can be replaced 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: To find the length of the longest substring where you can replace up to k characters to make all characters the same.
• Example:
  • Input: str = "ABAB", k = 2
  • Process: Use a sliding window to find the longest substring where the number of characters not equal to the most frequent character is less than or equal to k.
  • Output: 4, because "ABAB" can be transformed to "AAAA" by replacing 2 characters.

---

Reverse Words in a String

Function: reverseWordsInString()

Description:

Reverses the order of words in the given string.

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 = c + word;
            } else {
                result = word + ' ' + result;
                word.clear();
            }
        }
        result = word + ' ' + result;
        cout << result;
    }
};

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

Explanation:

• Purpose: To reverse the order of words in the string while keeping the characters in each word unchanged.
• Example:
  • Input: s = "hello world"
  • Process: Build words in reverse order and prepend to the result.
  • Output: "world hello"

---

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: To reverse the characters of each individual word in the string.
• Example:
  • Input: s = "hello world"
  • Process: Reverse each word independently and concatenate them with spaces.
  • Output: "olleh dlrow"

---

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: To find the length of the longest substring containing exactly k unique characters.
• Example:
  • Input: s = "abcabcbb", k = 2
  • Process: Use a sliding window to count unique characters and adjust the window to maintain exactly k unique characters.
  • Output: 4, because "bcbc" is the longest substring with exactly 2 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: To find the length of the longest substring without repeating characters.
• Example:
  • Input: s = "abcabcbb"
  • Process: Use a sliding window to track the last index of each character and adjust the window to avoid duplicates.
  • Output: 3, because "abc" is the longest substring without repeating characters.

---

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: To count the number of unique characters in a string.
• Example:
  • Input: s = "ababababa"
  • Process: Insert each character into a set, which automatically handles duplicates.
  • Output: 2, because the unique characters are 'a' and 'b'.