Question

Microsoft | OA Coding Questions and Solutions | Set - 44 | 2022

Answer 1

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.

Answer 2

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;
   }