HackerRank Two Characters Problem Solution
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
5Explanation
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.
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
