HackerRank — Alternating Characters Solution in Java

Problem Description

You are given a string containing characters and only. Your task is to change it into a string such that there are no matching adjacent characters. To do this, you are allowed to delete zero or more characters in the string.

Your task is to find the minimum number of required deletions.

Example

Remove an at positions and to make in deletions.

Function Description

Complete the alternatingCharacters function in the editor below.

alternatingCharacters has the following parameter(s):

• string s: a string

Returns

• int: the minimum number of deletions required

Input Format

The first line contains an integer, the number of queries.
The next lines each contain a string to analyze.

Constraints

• 1 ≤ q ≤ 10
• 1 ≤ length of s ≤ 10⁵
• Each string will consist only of characters A and B

Sample Input

5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB

Sample Output

3
4
0
0
4

Explanation

The characters marked red are the ones that can be deleted so that the string does not have matching adjacent characters.

My approach

So, basically, the gist of the problem is to figure out how many pairs of consequtive identical letters are there in the string. Every time you find a character that is the same as the last character you accepted for your string, you need to delete that character. That line of thought just screamed out the “stack” data structure.

This is my attempted solution in Java:

static int alternatingCharacters(String s) {
   Stack<Character> stack = new Stack<Character>();
   stack.push(s.charAt(0));
   int deletions = 0;
   for(int i=1; i<s.length(); i++){
    if(stack.peek() == s.charAt(i))
     deletions++;
    else
     stack.push(s.charAt(i));
   }
return deletions;
}

Explanation

So, I first push the first character of the string s onto my stack. That is because I must always keep the first character of my string in my alternatingCharacter string. So, once I have that pushed, I enter a for-loop that loops through the length of the string, starting from index 1.

For every character starting from index 1, I check if the character is the same as the top of the stack using the stack.peek() method. If it is, I increment deletions by 1. If not, I accept that character and push it onto my stack so that in the next iteration, I will be comparing the next character with this character. This way, I will end up with a string in my stack with perfectly alternating characters. Since the requirement of this problem was to simply return the number of characters deleted, that's what my function returns.

Final Comments

This was a relatively easy problem, which took me less than 15 minutes to pass all the test cases. Hope this helps. Please feel free to comment if you find a solution with greater optimization. Thanks.