HackerRank Two Characters Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Two Characters Problem Solution.

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 strings, 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.

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.

HackerRank Two Characters Problem Solution
HackerRank Two Characters Problem Solution

Two Characters C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>


int testaxy(char x, char y, char*s) {
    
    int i=0, lx=1, ly=1, str=0;
    
    while (s[i]) {
        if (s[i] == x)
            if (ly)
                str++, ly=0, lx=1;
            else
                return 0;
        else if(s[i] == y)
                if (lx)
                    str++, lx=0, ly=1;
                else
                  return 0;
        i++;     
    }
    
    if (str>1) return str;
    return 0;

}


int testastr(char x, char y, char*s, int*c) {
    if ( ((c[x-0x61]) == (c[y-0x61])) || ((c[x-0x61]) == (c[y-0x61]+1)) || ((c[x-0x61]) == (c[y-0x61])))
        return (testaxy(x, y, s));
    return 0;
}

int main(){
    int len; 
    scanf("%d",&len);
    char* s = (char *)malloc(512000 * sizeof(char));
    scanf("%s",s);
    
    int c[26];
    int maxstr = 0, lstrxy;
   
    for (int i=0; i<26 ; i++) c[i] = 0; /* zera contador de char */
        
    for (int i=0; s[i]; i++) c[s[i]-0x61]++; /* conta char */
    
    for (int x=0; x<26; x++)
        for (int y=0; y<26; y++)
          if (c[x] && c[y]) { /* par de char a analisar */
             int lstrxy = testastr(x+0x61,y+0x61,s,c);
             if (lstrxy > maxstr) maxstr = lstrxy;
          }
    

    printf("%d", maxstr);
    
    return 0;
}

Two Characters C++ Solution

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <sstream>
#include <ctime>
#include <memory.h>
#include <assert.h>
#include <unordered_map>
#include <limits.h>
#include <bitset>
#include <unordered_set>
using namespace std;

const long long bs = 1000000007;

static const int INF = 0x3f3f3f3f; 
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;


typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > vvi;

#define REP(i, n) for (int i=0; i < (int)(n); ++i)
#define pb push_back
#define mp make_pair
#define PI 3.14159265

struct cmp {
  bool operator()(int &a, int &b) { return a < b; }
};


int main() {
  int n; cin >> n;
  string s; cin >> s;

  int ans = 0;
  for (int i = 0; i < 26; i++) {
    for (int j = 0; j < 26; j++) {
      if (i == j) continue;
      int len = 0;
      int next = i;
      for (int k = 0; k < s.size(); k++) {

        if (s[k] -'a' == next) {
          len++;
          next = (i==next) ? j : i;
        } else if (s[k] -'a' == ((i==next) ? j : i)) {
          len = 0;
          break;
        }
      }

      ans = max(len, ans);
    }
  }
  if ( ans == 1) ans = 0;
  cout << ans;
  return 0;
}

Two Characters C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

class Solution 
{
    //static string  char[]
    
    static void Main(String[] args) 
    {
        Convert.ToInt32(Console.ReadLine());
        string s = Console.ReadLine();
        var cl = s.Distinct();
        List<char> wl = cl.ToList();
        List<char> bl = new List<char>();
        int rl = 0;
        
        
        
        while(Regex.Match(s, @"(.)\1", RegexOptions.IgnoreCase).ToString() != "")
        {
            foreach(var c in wl)
                if(s.Contains(c.ToString() + c.ToString()))
                    bl.Add(c);
                
                foreach(var c in bl)
                {
                    s = s.Replace(c.ToString(),"");
                    wl.Remove(c);
                }
        }
        
        //Console.WriteLine(s);
        if(cl.Count() - bl.Count() == 2)
        {
            rl = s.Length;
        }
        else
        {
        string ss = "";
            
            for(int i = 0; i < wl.Count(); i ++)
            {
                for(int j = i+1; j < wl.Count(); j ++)
                {
                    ss = s;
                    foreach(char c in wl)
                    {
                        if(c != wl[i] && c != wl[j])
                          ss = ss.Replace(c.ToString(), "");
                    }
                    if(Regex.Match(ss, @"(.)\1", RegexOptions.IgnoreCase).ToString() == "")
                        if(rl < ss.Length)
                        {
                            rl = ss.Length;
                        }
                    }
                }
            }
            
            Console.WriteLine(rl);
            
        }
    }

Two Characters Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'alternate' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int alternate(String s) {

        List<Character> chars = new ArrayList<>();
        
        while(true){

            List<Character> remove = new ArrayList<>();

            char last = ' ';
            for(int i = 0; i < s.length(); i++){

                char c = s.charAt(i);

                if(c == last){
                    remove.add(c);
                } else if(!chars.contains(c)){
                    chars.add(c);
                }
                last = c;

            }

            if(remove.size() == 0)
                break;

            for(char r : remove){
                s = removeChar(s, r);
                chars.remove((Character)r);
            }
            
        }

        int len = chars.size();
        boolean good = true;
        for(int i = 0; i < len; i++){

            for(int j = i+1; j < len; j++){

                char c1 = chars.get(i);
                char c2 = chars.get(j);

                String s2 = new StringBuilder(s).toString();
                for(char c : chars){
                    if(c != c1 && c != c2)
                        s2 = removeChar(s2, c);
                }

                char last = ' ';
                for(char c : s2.toCharArray()){
                    
                    if(c == last){
                        good = false;
                        break;
                    }                        
                    last = c;
                }

                if(good && s2.length() > maxString)
                    maxString = s2.length();

                good = true;
            
            }

        }



        //recurse(s, chars);

        return maxString;

    }

    static int maxString = 0;

    static void recurse(String s, List<Character> chars){

        char last = ' ';
        for(char c : s.toCharArray()){

            if(c == last)
                return;

            last = c;
        }

        if(chars.size() == 2){
            
            if(s.length() > maxString)
                maxString = s.length();

            return;
        }

        List<Character> chars2 = new ArrayList<>(chars);
        List<Character> used = new ArrayList<>();
        for(char c : chars){
            if(containsChar(s, c) && !used.contains(c)){
                chars2.remove((Character)c);
                used.add(c);
                recurse(removeChar(s, c), chars2);
                chars2.add(c);
            }
        }


    }

    static boolean containsChar(String s, char c){
        int l = s.length();
        for(int i = 0; i < l; i++){

            if(s.charAt(i) == c)
                return true;
        }

        return false;
    }

    static String removeChar(String s, char c){
        StringBuilder sb = new StringBuilder(s);
        
        for(int i = 0; i < sb.length(); i++){
            if(sb.charAt(i) == c){
                sb.deleteCharAt(i);
                i--;
            }
        }

        return sb.toString();
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int l = Integer.parseInt(bufferedReader.readLine().trim());

        String s = bufferedReader.readLine();

        int result = Result.alternate(s);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Two Characters JavaScript Solution

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var len = parseInt(readLine());
    var s = readLine();
    //var s = 'mbmmbmbmbb'
    //var s = 'muqqzbcjmyknwlmlcfqjujabwtekovkwsfjrwmswqfurtpahkdyqdttizqbkrsmfpxchbjrbvcu';
    //var s = 'bbbbeabeefeab';
    var count = 0;
    var final_arr = {};
    for (var i = 0; i < s.length; i++) {
        for (var a = i + 1; a < s.length; a++) {
            var one_arr = [];
            var new_count = 0;
            for (var e = 0; e < s.length; e++) {
                if (s[e] === s[i] || s[e] === s[a]) {
                    new_count++;
                    one_arr.push(s[e]);
                }
            }
            
            var check_invalidity = 0;
            if (one_arr) {
                for (var u = 0; u < one_arr.length; u++) {
                    if (one_arr[u] == one_arr[u + 1]) {
                        check_invalidity = 1;
                    }
                }
            }
            
            if (check_invalidity == 0 && new_count > count) {
                count = new_count;
                final_arr = one_arr;
            } 
        }
    }
    console.log(count);
    
}

Two Characters Python Solution

n = int(input())
s = input()

def check_valid(s):
    if len(s) >= 2:
        first = s[0]
        second = s[1]
        if first != second:
            for count, i in enumerate(list(s)):
                # print(count, i)
                if count%2 == 0:
                    if i != first:
                        return False
                else:
                    if i != second:
                        return False
            return True
    return False

def replace_chain(s, lista):
    for l in lista:
        s = s.replace(l, '')
    return s



to_delete = set(s)
# print(to_delete)
biggest = 0
for first in to_delete:
    for second in to_delete:
        if first!=second:
            new_to_delete = set(to_delete)
            new_to_delete.remove(first)
            new_to_delete.remove(second)
            new_s = replace_chain(s, new_to_delete)
            # print(new_s)
            if check_valid(new_s):
                if len(new_s) > biggest:
                    biggest = len(new_s)
                    # print(new_s)

print(biggest)

Other Solutions

c C# C++ HackerRank Solutions java javascript python

Leave a Reply