Skip to main content

11.2 String Comparison

242. Valid Anagram​

Problem Description​

Determine if two strings contain exactly the same characters.

Input and Output Example​

Input two strings and output a boolean indicating whether the two strings meet the condition.

Input: s = "anagram", t = "nagaram"
Output: true

Solution Explanation​

We can use a hash table or an array to count the frequency of each character in both strings. If the frequencies match, it means the strings contain the exact same characters.

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    vector<int> counts(26, 0);
    for (int i = 0; i < s.length(); ++i) {
        ++counts[s[i] - ’a’];
        --counts[t[i] - ’a’];
    }
    return all_of(counts.begin(), counts.end(), [](int c) { return c == 0; });
}

205. Isomorphic Strings​

Problem Description​

Determine if two strings are isomorphic. Two strings are isomorphic if characters in one string can be replaced to get the other string, while ensuring that no two different characters map to the same character.

Input and Output Example​

Input two strings and output a boolean indicating whether they meet the condition.

Input: s = "paper", t = "title"
Output: true

In this example, by replacing p, a, e, r in s with t, i, l, e respectively, the two strings can become identical.

Solution Explanation​

We can reformulate the problem: track the first appearance position of each character in both strings. If the characters at the same position in both strings have the same first appearance position, the strings are isomorphic.

For example, for "paper" and "title," if we reach the third characters p and t, we find their first appearances are at the first character, which satisfies the isomorphic condition. We can use a hash table for storage or a fixed-length array of size 128 (for the total number of ASCII characters).

bool isIsomorphic(string s, string t) {
    vector<int> s_init(128, 0), t_init(128, 0);
    for (int i = 0; i < s.length(); ++i) {
        if (s_init[s[i]] != t_init[t[i]]) {
            return false;
        }
        s_init[s[i]] = t_init[t[i]] = i + 1;
    }
    return true;
}

647. Palindromic Substrings​

Problem Description​

Given a string, find how many of its substrings are palindromic. A palindrome is defined as being symmetric from left to right.

Input and Output Example​

Input is a string, and output is an integer representing the count of palindromic substrings.

Input: "aaa"
Output: 6

The six palindromic substrings are ["a", "a", "a", "aa", "aa", "aaa"].

Solution Explanation​

We can start from every position in the string and extend to the left and right, counting how many palindromic substrings have the current position as their center.

// Auxiliary function
int extendSubstrings(string s, int l, int r) {
    int count = 0, n = s.length();
    while (l >= 0 && r < n && s[l] == s[r]) {
        --l;
        ++r;
        ++count;
    }
    return count;
}
// Main function
int countSubstrings(string s) {
    int count = 0;
    for (int i = 0; i < s.length(); ++i) {
        count += extendSubstrings(s, i, i);      // Odd length
        count += extendSubstrings(s, i, i + 1);  // Even length
    }
    return count;
}

696. Count Binary Substrings​

Problem Description​

Given a binary string (composed of '0's and '1's), count the number of non-empty substrings where the number of '0's and '1's are equal, and all '0's and '1's must appear consecutively (e.g., "0011", "1100"; but "0101" is not valid).

Input and Output Example​

Input is a string, and output is an integer representing the count of valid substrings.

Input: "00110011"
Output: 6

In this example, the six substrings where '0's and '1's are equal are ["0011", "01", "1100", "10", "0011", "01"].

Solution Explanation​

Traverse the string from left to right, keeping track of the length of consecutive characters that are the same as the current character, as well as the length of the consecutive different characters before it. For example, in "00110", the last '0' has:

  • A consecutive length of 1 for '0', because there's only one '0' at the end.
  • A consecutive length of 2 for '1', because there are two '1's right before it.

If the length of the consecutive different characters is greater than or equal to the current consecutive length, then there exists exactly one valid substring ending at the current character.

int countBinarySubstrings(string s) {
    int prev = 0, cur = 1, count = 0;
    for (int i = 1; i < s.length(); ++i) {
        if (s[i] == s[i - 1]) {
            ++cur;
        } else {
            prev = cur;
            cur = 1;
        }
        if (prev >= cur) {
            ++count;
        }
    }
    return count;
}

1249. Minimum Remove to Make Valid Parentheses​

Problem Description​

Given a string containing letters and parentheses, determine the minimum number of parentheses to remove to make the string valid.

Input and Output Example​

Input is a string, and output is a valid string with the longest possible length after removal.

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

Returning "lee(t(co)de)" or "lee(t(c)ode)" is also considered correct.

Solution Explanation​

Since only one type of parenthesis is involved, we don't necessarily need a stack to track them. Instead, we can use a temporary variable to count how many more left parentheses are present than right parentheses at any position.

  • If this count becomes negative during traversal, it means there are extra right parentheses that need to be removed.
  • At the end of the traversal, if the count is positive, it means there are extra left parentheses that need to be removed by traversing from right to left.

A small optimization here is to first mark all positions that need to be removed and then remove them in one go.

string minRemoveToMakeValid(string s) {
    int count = 0, n = s.length();
    char to_delete = '#';
    for (char& c : s) {
        if (c == '(') { 
            ++count; 
        } else if (c == ')') {
            if (count > 0) {
                --count;
            } else {
                c = to_delete;
            }
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        if (count == 0) break;
        if (s[i] == '(') {
            s[i] = to_delete;
            --count;
        }
    }
    s.erase(remove_if(s.begin(), s.end(),
                      [to_delete](char c) { return c == to_delete; }),
            s.end());
    return s;
}