Created
December 28, 2011 18:28
-
-
Save phaniram/1529028 to your computer and use it in GitHub Desktop.
Interview Street Challenges-String reduction
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package interviewstreet; | |
| import java.util.Arrays; | |
| import java.util.Scanner; | |
| public class Solution { | |
| int min=1; | |
| int val=1; | |
| public static void main(String[] args) { | |
| Scanner scanner; | |
| Solution sr = new Solution(); | |
| scanner = new Scanner(System.in); | |
| int no_cases = scanner.nextInt(); | |
| for (int i = 0; i < no_cases; i++) { | |
| String to_proc = scanner.next(); | |
| sr.solve(to_proc); | |
| System.out.println(sr.min); | |
| } | |
| } | |
| private boolean solve(String to_proc) { | |
| char[] ary=to_proc.toCharArray(); | |
| int len=ary.length; | |
| min =ary.length; | |
| if(ary.length==1) | |
| { | |
| val=1; | |
| return true; | |
| } | |
| if(ary.length==2 && ary[0]==ary[1]) | |
| { | |
| val=2; | |
| return true; | |
| } | |
| for(int i=0;i<ary.length-1;i++) | |
| { | |
| if(ary[i]!=ary[i+1]) | |
| { | |
| String build=Character.toString(ary[i]).concat(Character.toString(ary[i+1])); | |
| char other_char =other(build); | |
| String one=""; | |
| String two=Character.toString(other_char); | |
| String three=""; | |
| if(i==1) | |
| { | |
| one=Character.toString(ary[0]); | |
| }else if(i>1) | |
| { | |
| one=new String(Arrays.copyOfRange(ary,0,i)); | |
| } | |
| if(i+2<len-1) | |
| { | |
| three=new String(Arrays.copyOfRange(ary,i+2,len)); | |
| }else if(i+2==len-1) | |
| { | |
| three=Character.toString(ary[i+2]); | |
| } | |
| String fin=one+two+three; | |
| // System.out.println(to_proc+" - "+fin); | |
| boolean stop=solve(fin); | |
| if(stop) | |
| { | |
| min=Math.min(min, val); | |
| return stop; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| private char other(String group_string) { | |
| char ret='b'; | |
| if (group_string.equalsIgnoreCase("ab")|| group_string.equalsIgnoreCase("ba")) { | |
| ret='c'; | |
| } else if (group_string.equalsIgnoreCase("bc")|| group_string.equalsIgnoreCase("cb")) { | |
| ret='a'; | |
| } | |
| return ret; | |
| } | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
String Reduction (25 Points)
Given a string consisting of a,b and c's, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if 'a' and 'c' are adjacent, they can replaced with 'b'. What is the smallest string which can result by applying this operation repeatedly?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains the string you start with.
Output:
Output T lines, one for each test case containing the smallest length of the resultant string after applying the operations optimally.
Constraints:
1 <= T <= 100
The string will have at most 100 characters.
Sample Input:
3
cab
bcab
ccccc
Sample Output:
2
1
5
Explanation:
For the first case, you can either get cab -> cc or cab -> bb, resulting in a string of length 2.
For the second case, one optimal solution is: bcab -> aab -> ac -> b. No more operations can be applied and the resultant string has length 1.
For the third case, no operations can be performed and so the answer is 5.