# 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:

staticintalternatingCharacters(String s) { Stack<Character> stack =newStack<Character>(); stack.push(s.charAt(0));intdeletions = 0;for(inti=1; i<s.length(); i++){if(stack.peek() == s.charAt(i)) deletions++;elsestack.push(s.charAt(i)); }returndeletions;}

**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.