Alternating Characters – HackerRank Solution

In this post, we will solve Alternating Characters HackerRank Solution. This problem (Alternating Characters) is a part of HackerRank Problem Solving series.

Task

You are given a string containing characters A and B 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

s = AABAAB

Remove an A at positions 0 and 3 to make s = ABAB in 2 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 q, the number of queries.
The next q lines each contain a string s to analyze.

Constraints

  • 1 <= q <= 10
  • 1 <= length of s <= 105
  • Each string s 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.

AAAA -> A (3 deletions)
BBBBB -> B (4 deletions)
ABABABAB -> ABABABAB (0 deletions)
BABABA -> BABABA (0 deletions)
AAABBB -> AB (4 deletions)

Solution – Alternating Characters – HackerRank Solution

C++

#include<iostream>
#include<string>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string str;
        cin >> str;
        int len = (int)str.size();
        int cnt = 0, ans = 0;
        for (int i = 0; i < len; i++)
        {
            if (i == 0 || str[i] == str[i - 1])
                cnt++;
            else
            {
                if (cnt > 1)
                {
                    ans += cnt - 1;
                }
                cnt = 1;
            }
        }
        if (cnt > 1)
        {
            ans += cnt - 1;
        }
        cout << ans << endl;
    }
    return 0;
}

Python

import os

# Complete the alternatingCharacters function below.
def alternatingCharacters(s):
    deletions = 0

    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            deletions += 1

    return deletions

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        s = input()

        result = alternatingCharacters(s)
        fptr.write(str(result) + '\n')

    fptr.close()

Java

import java.util.Scanner;

public class Solution {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int T = in.nextInt();
		for (int tc = 0; tc < T; tc++) {
			String str = in.next();
			System.out.println(Math.min(countDeletion(str, 'A'), countDeletion(str, 'B')));
		}

		in.close();
	}

	static int countDeletion(String str, char target) {
		int deletionNum = 0;
		boolean match = true;
		for (int i = 0; i < str.length(); i++) {
			if ((str.charAt(i) == target) == match) {
				match = !match;
			} else {
				deletionNum++;
			}
		}
		return deletionNum;
	}
}

Note: This problem (Alternating Characters) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *