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.


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


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


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

Sample Input


Sample Output



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;}


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.




Software Engineer at Headstorm

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Nativescript VS React Native: Overview and Comparison

Coloring Your Terminal Using Nodejs

Building a React Autocomplete Component from scratch

How to parallel run MatLab code via MatLab code?

Frontend for backend developers

Asynchronous functions in JS

Re-visiting Removing Elements from a State Array

How to integrate SendGrid in Node.js (typescript)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Adrika Khan

Adrika Khan

Software Engineer at Headstorm

More from Medium

Electronics Shop | HackerRank Problem | Java Solutions

Multi-threading In Java (i)

Profile Java Applications using VisualVM

Getting started with SpringBoot