exp 10+
time limit 100mins
1st question:
input string contains 'a' and 'b'. blocks are defined as contiguos elements which have same alphabets. eg, i/p babaa has 4 blocks b, a, b, aa.
number of inserts required to make all blocks of equal length.
public int solution(String S) {
char[] myArray = S.toCharArray();
List<Integer> blockInfo = new ArrayList<>();
char previous = myArray[0];
int previousLength =1;
int length = myArray.length;
for(int i=1; i<length; i++){
if(myArray[i] == previous){
previousLength++;
} else {
blockInfo.add(previousLength);
previous = myArray[i];
previousLength = 1;
}
}
blockInfo.add(previousLength);
int max = blockInfo.get(0);
for(int i=0; i<blockInfo.size(); i++){
if(max < blockInfo.get(i)){
max = blockInfo.get(i);
}
}
int count = 0 ;
for(int i=0; i< blockInfo.size(); i++){
count += (max - blockInfo.get(i));
}
return count;
}
2nd question:
input string consists of alphabets 'a' and 'b'. how many number of ways to dived the string into 3 parts so that all the three parts have same number of 'a' s.
public int solution(String S) {
if(S== null || S.equals(""))
return 0;
int[] count = new int[1];
bt(S, new ArrayList<>(), 2, count);
return count[0];
}
private void bt(String remainingString, List<String> currentList, int cutremaining, int[] count){
if(cutremaining >= 0 && remainingString.equals("")){
return;
}
if(cutremaining == 0){
currentList.add(remainingString);
if(isValid(currentList)){
count[0]++;
}
currentList.remove(currentList.size()-1);
return;
}
for(int i=0; i<remainingString.length(); i++){
String thisCut = remainingString.substring(0, i+1);
currentList.add(thisCut);
String remaingCutString = remainingString.substring(i+1);
bt(remaingCutString, currentList, cutremaining -1, count);
currentList.remove(currentList.size()-1);
}
}
public boolean isValid(List<String> list){
Set<Integer> uniqueCount = new HashSet<>();
for(int i=0; i< list.size(); i++){
String current= list.get(i);
int count = 0;
for(int j=0; j<current.length(); j++){
if(current.charAt(j) == 'a'){
count++;
}
}
uniqueCount.add(count);
}
if(uniqueCount.size() > 1)
return false;
return true;
}
Comments (4)