Interviewstreet String Reduction Solution C++

Interviewstreet Challenge String Reduction

Problem Statement

You are given a string consisting of a, b, and c's and following operation is allowed: Take any two adjacent character and they can be replaced with third character. For ex: a and b with c, b and c with a. Find length of smallest string, the operation can be applied repeatedly.
Ex: for input bcab, bcab -> aab -> ac -> b the output will be 1

Input: T test cases and next T lines contain strings to start with.
Output: T lines containing length of smallest possible resultant strings after applying operations repeatedly and optimally.

Algorithm

Use brute force approach, For each string
1) If length of string is 1 return 1
2) if len is 2 and both character are same return 2
3) else try to find smallest possible string from all possible ways i.e for every two adjacent character replace it with third character and invoke reduce again on this new smaller string until smallest possible string is reached.
4) If the string achieved is smaller then previous possible smaller string store and update minimum length.

If you have a different approach in mind, please share it in comments section for our readers.

Solution

// all 10 test cases passed

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

int minimum=1;
int value=1;


private boolean reduce(String s1) {
char[] array=s1.toCharArray();
int len=array.length;
minimum =array.length;
boolean flag;
String cat;
if(len==1)
{
value=1;
return true;
}
else if(array[0]==array[1] && len == 2)
{
value=2;
return true;
}

for(int i=0;i<len-1;i++)
{
if(array[i+1]!=array[i])
{

String new_string

=Character.toString(array[i]).concat(Character.toString(array[i+1]));
char reduce =other(new_string);
String sub1="";
String sub2=Character.toString(reduce);
String sub3="";
if(i==1)
{
sub1=Character.toString(array[0]);
}else if(i>1)
{
sub1=s1.substring(0, i);
}
if(i+2<len-1)
{
sub3=s1.substring(i+2,len);
}else if(i+2==len-1)
{
sub3=Character.toString(array[i+2]);
}
cat=sub1+sub2+sub3;
flag=reduce(cat);
if(flag)
{
minimum=Math.min(minimum, value);
return flag;
}
}
}
return false;
}

private char other(String s1) {
char ret_value='b';
if (s1.equalsIgnoreCase("bc")|| s1.equalsIgnoreCase("cb")) {
ret_value='a';
}
else if (s1.equalsIgnoreCase("ab")|| s1.equalsIgnoreCase("ba")) {
ret_value='c';
}
return ret_value;
}
   
   
public static void main(String[] args) {
Scanner scan;
Solution obj = new Solution();
scan = new Scanner(System.in);
int T = scan.nextInt();
for (int i = 0; i < T; i++) {
String s1 = scan.next();
obj.reduce(s1);
System.out.println(obj.minimum);
}
}
       
}

Time Complexity

In a string of length n, there are n-1 2 character pairs, At max each of these pair would contain different character so for n-1 pairs we replace it with third character and call reduce again on new string of length n-1 which has n-2 pairs and so on....(n-1)*(n-2)*(n-3)..1 = (n-1)! times.
Surely it can be done in better way. If you find a better solution, update me.