HackerRank Alternating Characters Solution in C++ | Approaches & Optimization

HackerRank Alternating Characters Problem Overview

The HackerRank Alternating Characters problem requires you to remove the minimum number of characters from a string so that no two identical characters are adjacent. The goal is to ensure that the resulting string alternates between different characters.

The input consists of a number of queries (q) followed by strings (s). For each string, you need to calculate and return the minimum number of deletions required to make it an alternating sequence of characters.

This problem is a great exercise in string manipulation and iteration logic. It helps you think about how to efficiently process strings and count necessary operations without extra space.

Problem Difficulty & Tags

The Alternating Characters problem on HackerRank is considered an Easy-level problem. It focuses on simple string processing and counting logic.

• Difficulty: Easy
• Tags: Strings, Iteration, Counting, String Manipulation

This problem is ideal for beginners to practice iterating through strings, applying simple conditions, and efficiently counting operations.

Understanding the Problem

The goal of the Alternating Characters problem is to ensure that a string has no two identical characters next to each other. For example, in the string "AABBA", there are consecutive duplicate characters that need to be removed.

For each string, you need to count the minimum number of deletions required to make it alternate properly. You are not required to output the new string—only the count of deletions.

Key points to understand:

• Check each character and compare it with the previous character.
• Every time a character is the same as the previous one, it counts as a deletion.
• The process continues until the end of the string, summing up all necessary deletions.

This understanding helps simplify the problem to a single linear scan of the string.

Approach and Logic Explanation

To solve the Alternating Characters problem efficiently, I used a simple linear scan of the string. Here’s the thought process:

1. Initialize a counter (cnt) to zero. This will track the number of deletions needed.
2. Iterate through the string from the second character to the end.
3. Compare the current character with the previous character.
   • If they are the same, increment the counter (cnt++) because this character needs to be removed.
   • If they are different, no deletion is needed, move to the next character.
4. After the loop ends, the counter (cnt) represents the minimum deletions required to make the string alternate.
5. Repeat this process for each query string provided.

This approach ensures O(n) time complexity per string and uses O(1) extra space, making it very efficient.

C++ Solution Code for Alternating Characters

Below is my C++ implementation for the Alternating Characters problem. It counts consecutive duplicate characters and returns the minimum number of deletions required.

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

string ltrim(const string &);
string rtrim(const string &);

int alternatingCharacters(string s) {
    int cnt = 0;
    for (size_t i = 1; i < s.size(); i++) { // use size_t for index
        if (s[i] == s[i-1]) {
            cnt++;
        }
    }
    return cnt;
}

int main() {
    ofstream fout(getenv("OUTPUT_PATH"));

    string q_temp;
    getline(cin, q_temp);

    int q = stoi(ltrim(rtrim(q_temp)));

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string s;
        getline(cin, s);

        int result = alternatingCharacters(s);

        fout << result << "\n";
    }

    fout.close();
    return 0;
}

string ltrim(const string &str) {
    string s(str);
    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), [](unsigned char ch) { return !isspace(ch); })
    );
    return s;
}

string rtrim(const string &str) {
    string s(str);
    s.erase(
        find_if(s.rbegin(), s.rend(), [](unsigned char ch) { return !isspace(ch); }).base(),
        s.end()
    );
    return s;
}

Step-by-Step Walkthrough

Let’s break down how the solution works using an example string:

Example String: "AABAAB"

1. Start with a counter cnt = 0 to track deletions.
2. Compare the second character with the first: "A" vs "A". They are the same, so increment cnt → cnt = 1.
3. Compare the third character "B" with the second "A". They are different, so no deletion is needed.
4. Compare the fourth character "A" with the third "B". Different, no deletion.
5. Compare the fifth character "A" with the fourth "A". Same, increment cnt → cnt = 2.
6. Compare the sixth character "B" with the fifth "A". Different, no deletion.

At the end, cnt = 2, which means we need to delete two characters to make the string alternate properly.

This linear scan ensures O(n) time complexity and requires only a single variable for counting, making it very efficient for large strings.

Sample Input & Output

Here’s an example illustrating how the input is processed and the corresponding output:

Time and Space Complexity of the C++ Solution

Time Complexity

The solution iterates through each character of the string exactly once. For a string of length n, the time complexity is O(n). Since we process each query independently, if there are q queries, the total time complexity is O(q * n), where n is the length of each individual string.

Space Complexity

The solution uses only a few integer variables (cnt and loop indices) and does not require any extra data structures proportional to the input size. Therefore, the space complexity is O(1).

This makes the solution both time and space efficient, suitable even for large input strings.

Alternative Approaches and Optimizations

Below are several ways to solve the Alternating Characters problem. Each approach includes a short description, its time & space complexity, and when you might prefer it. The greedy single-pass or run-length approach is usually the simplest and fastest in practice.

// C++ (greedy single-pass)
int alternatingDeletions(const string &s) {
    int deletions = 0;
    for (int i = 1; i < (int)s.size(); ++i) {
        if (s[i] == s[i-1]) ++deletions;
    }
    return deletions;
}

# Python (run-length)
def alternating_deletions(s: str) -> int:
    if not s:
        return 0
    deletions = 0
    run_len = 1
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            run_len += 1
        else:
            deletions += run_len - 1
            run_len = 1
    deletions += run_len - 1
    return deletions

// Java (stack-based)
int alternatingDeletionsStack(String s) {
    java.util.Deque stack = new java.util.ArrayDeque<>();
    int deletions = 0;
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() == c) {
            deletions++;
        } else {
            stack.push(c);
        }
    }
    return deletions;
}

Mistakes to Avoid & Tips

Related String Manipulation Problems on HackerRank

If you enjoyed solving Alternating Characters, here are some similar string manipulation problems you might find interesting:

• Making Anagrams
• Game of Thrones - I
• String Construction
• Explore more String problems on HackerRank

Conclusion

Solving the HackerRank Alternating Characters problem helps strengthen your understanding of string manipulation and linear scanning techniques. By simply iterating through the string and comparing each character with the previous one, we can efficiently count the minimum number of deletions required to make the string alternate.

Key takeaways from this problem:

• Linear scans are often sufficient for problems involving consecutive elements in a string.
• Counting operations instead of modifying the string avoids complications with indexing.
• Consider edge cases such as strings that are already alternating or have all identical characters.
• The solution has O(n) time complexity and O(1) space complexity, making it very efficient.

I encourage you to try more string manipulation problems on HackerRank to improve your problem-solving skills and get comfortable with optimizing both time and space complexity.