algoadvance

Leetcode 3019. Number of Changing Keys

Problem Statement

You are given a string s that contains only lowercase English letters. A “changing key-out” substring is one that contains a sequence of characters where each character appears the same number of times. Your task is to find the number of such substrings in the string s.

Clarifying Questions

1. Constraints: What is the length of the string s?
   • This helps in determining the approach and efficiency we need.
2. Output: Should the output be the number of substrings, or should we print each substring?
   • Here, the problem seems to ask for a count.
3. Edge Cases: Are there any specific edge cases we should consider such as an empty string or a string with a single character?

For this example, I will assume:

• Length of s is within reasonable limits for typical coding interviews (e.g., up to 10^5).
• Only the count of substrings is required.
• Standard edge cases (like empty strings) will be taken into consideration.

Strategy

1. Initialize: Create a map to store the frequency of characters in the current window.
2. Two-pointer Technique: Use two pointers (say left and right) to represent the current window of the substring.
3. Balance Checking: For each character added to the window, check if the current window is a valid “changing key-out” substring.
4. Expand and Contract: Expand the right pointer to include more characters in the window; contract the left pointer to reduce from the left when the substring is valid.
5. Count Substrings: Keep a count of valid substrings found during the process.

Code

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

using namespace std;

bool is_valid(const unordered_map<char, int>& freq) {
    if (freq.empty()) return true;
    int count = freq.begin()->second;
    for (const auto& [char_, cnt] : freq) {
        if (cnt != count) return false;
    }
    return true;
}

int countChangingKeyOutSubstrings(const string& s) {
    int n = s.size();
    int count = 0;

    for (int start = 0; start < n; ++start) {
        unordered_map<char, int> freq;
        for (int end = start; end < n; ++end) {
            freq[s[end]]++;
            if (is_valid(freq)) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    string s;
    cout << "Enter the string: ";
    cin >> s;

    cout << "Number of changing key-out substrings: " << countChangingKeyOutSubstrings(s) << endl;

    return 0;
}

Time Complexity

• Outer Loop: Runs n times representing the start pointer.
• Inner Loop: In the worst case, this runs n times for each start position.
• Validation: Validating the current window to ensure equality of character counts takes O(26) i.e., O(1) time since there are at most 26 lowercase English letters.

Therefore, the overall time complexity is O(n^2). This is efficient enough given our constraints within typical coding interviews.

Edge Cases:

• Empty String: The function will correctly return 0.
• Single Character String: This will return 1.

This approach ensures all substrings are correctly evaluated for the frequency property, and counts are maintained efficiently using hashing (unordered_map).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?