Two Characters – HackerRank Solution

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

Task

Given a string, remove characters until the string is made up of any two alternating characters. When you choose a character to remove, all instances of that character must be removed. Determine the longest string possible that contains just two alternating letters.

Example

s = ‘abaacdabd’

Delete a, to leave bcdbd. Now, remove the character c to leave the valid string bdbd with a length of 4. Removing either b or d at any point would not result in a valid string. Return 4.

Given a string s, convert it to the longest possible string t made up only of alternating characters. Return the length of string t. If no string t can be formed, return 0.

Function Description

Complete the alternate function in the editor below.

alternate has the following parameter(s):

• string s: a string

Returns.

• int: the length of the longest valid string, or 0 if there are none

Input Format

The first line contains a single integer that denotes the length of s.
The second line contains string s.

Constraints

• 1 <= length of s <= 1000
• s[i] ∈ ascii[a – z]

Sample Input

STDIN       Function
-----       --------
10          length of s = 10
beabeefeab  s = 'beabeefeab'

Sample Output

5

Explanation

The characters present in s are a, b, e, and f. This means that t must consist of two of those characters and we must delete two others. Our choices for characters to leave are [a,b], [a,e], [a, f], [b, e], [b, f] and [e, f].

If we delete e and f, the resulting string is babab. This is a valid t as there are only two distinct characters (a and b), and they are alternating within the string.

If we delete a and f, the resulting string is bebeeeb. This is not a valid string t because there are consecutive e‘s present. Removing them would leave consecutive b's, so this fails to produce a valid string t.

Other cases are solved similarly.

babab is the longest string we can create.

Solution – Two Characters – HackerRank Solution

C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

int main() {
    int n; std::cin >> n; /* useless to us, but whatever... */
    std::string s; std::cin >> s;

    std::vector<int> freq(26,0);
    for (const char& c : s) freq[c-'a']++;

    int max = 0;
    char last;
    bool valid;

    for (int i = 0; i < freq.size(); i++) {
        if (freq[i] == 0) continue;

        for (int j = i+1; j < freq.size(); j++) {

            if (freq[j] == 0) continue;

            last = -1;
            valid = true;
            for (const char& c : s) {
                if (c == char(i+'a') || c == char(j+'a')) {
                    if (last == c) {
                        valid = false;
                        break;
                    }
                    last = c;
                }
            }

            if (valid && std::abs(freq[i] - freq[j]) <= 1)
                max = std::max(max, freq[i] + freq[j]);
        }
    }
    std::cout << max << std::endl;

    return 0;
}

Python

import sys
from itertools import combinations

def validate(string):
    for ind in range(len(string)-1):
        if string[ind] == string[ind + 1]:
            return False
    return True

def twoCharaters(string):
    str_set = set(list(string))
    variants = combinations(str_set, 2)
    max_res = 0
    
    for comb in variants:
        t = [c for c in string if c == comb[0] or c == comb[1]]
        #print("comb = {} t = {}".format(comb, t))
        if validate(t):
            max_res = max(max_res, len(t))
        
    return max_res
    

if __name__ == "__main__":
    l = int(input().strip())
    s = input().strip()
    result = twoCharaters(s)
    print(result)

Java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        String s = in.next();
        int maxPattern = 0;
        
        if(s.length() == 1)//Edge case where length is 1
        {
            System.out.println(maxPattern);
            System.exit(0);
        }
        
        //Loop through all letter pairs
        for(int i = 0; i < 26; i++)
        {
            nextLetter:
            for(int j = i + 1; j < 26; j++)
            {
                char one = (char) ('a' + i); //First char in pair
                char two = (char) ('a' + j); //Second char in pair
                char lastSeen = '\u0000';
                int patternLength = 0;
                
                for(char letter : s.toCharArray())
                {
                    if(letter == one || letter == two)
                    {
                        if(letter == lastSeen)//Duplicate found
                        {
                            continue nextLetter;
                        }
                        //Not a duplicate
                        patternLength++;
                        lastSeen = letter;
                    }
                }//for char : s
                
                maxPattern = (patternLength > maxPattern) ? patternLength : maxPattern; //Keep a running max
                
            }//for j
        }//for i
        
        System.out.println(maxPattern);
        
    }
}

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