algoadvance

Leetcode 3206. Alternating Groups I

Problem Statement

Given a string s, return an array representing the length of each consecutive group of characters that alternate between letters and digits. For example, for the string “a1b2c3”, the groups are “a”, “1”, “b”, “2”, “c”, “3”, so the result should be [1, 1, 1, 1, 1, 1].

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of the string s?
    • Can the input string contain special characters or spaces?
  2. Output Format:
    • Should the output always be an array of integers?
    • If the string contains neither letters nor digits (e.g., empty string), should the result be an empty array?

Sample Input and Output

Strategy

  1. Initialize Variables:
    • Use a vector to store the lengths of each alternating group.
    • A variable to keep track of the current group length.
  2. Iterate through the string:
    • Identify the current character as either a digit or letter.
    • Compare it with the previous character type.
    • If the character type alternates, push the current group length to the vector and reset the group length.
    • Continue the above until the end of the string.
  3. Edge Cases:
    • Handle single character strings.
    • Handle strings that are purely letters or digits.

Code

Here’s the C++ implementation:

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

std::vector<int> alternatingGroups(const std::string& s) {
    std::vector<int> result;
    if (s.empty()) return result;

    // Initialize the first group length
    int groupLength = 1;

    // Identify if the first character is a digit or a letter
    bool isCurrentDigit = isdigit(s[0]);

    for (size_t i = 1; i < s.size(); ++i) {
        // Check if the character type has changed
        if ((isCurrentDigit && isalpha(s[i])) || (!isCurrentDigit && isdigit(s[i]))) {
            // Add the current group length to the result
            result.push_back(groupLength);

            // Reset the group length
            groupLength = 1;

            // Update the current type flag
            isCurrentDigit = !isCurrentDigit;
        } else {
            // Increment the current group length
            groupLength++;
        }
    }

    // Add the last group length to the result
    result.push_back(groupLength);

    return result;
}

int main() {
    std::string input = "a12b3c4";
    std::vector<int> output = alternatingGroups(input);
    
    // Print the result
    for (int length : output) {
        std::cout << length << " ";
    }
    
    return 0;
}

Time Complexity

Explanation of Code:

  1. Initial Checks:
    • If the string is empty, return an empty vector.
    • Initialize a starting group length.
  2. Iterate Through the String:
    • For each character, check if the type (digit or letter) has changed from the previous character.
    • If it has changed, append the current group length to the result vector and reset the group length.
  3. Final Step:
    • Don’t forget to append the length of the last group after exiting the loop.

This code correctly handles the grouping and tracking of alternating letters and digits.

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