Question

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

Answer 1

I got this question in Microsoft OA and it took me a lot of time and i couldn't do it. Can anyone please help me with an optimized approach or code for the following question :

 

 

Thanks in advance!

Answer 2

Set the relevant char's to zero and return new String instead of StringBuilder. Don't think it reduces the complexity though.

 

public static String solution(String s){
        char str [] = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=1 ; i < s.length() ; i++){
            char c = str[i];
        
            if(!stack.isEmpty()) {
                char prev = str[stack.peek()];
                if(replace(str, c, prev)){
                    str[i] = 0;
                    str[stack.pop()] = 0;
                    continue;
                }
            }
            stack.push(i);
            
        }
        return new String(str);
    }

Answer 3

Simple stack based solution.

 

    Stack stack = new Stack<>();
    StringBuffer result =new StringBuffer();
    for(Character c : s.toCharArray()){
        if(stack.isEmpty())
            stack.add(c);
        else{
            if((c == 'A' && stack.peek() == 'B') || (c == 'B' && stack.peek()=='A')){
                stack.pop();
            }else if((c == 'C' && stack.peek() == 'D') || (c == 'D' && stack.peek()=='C')){
                stack.pop();
            }else{
                stack.add(c);
            }
        }
    }
    while(!stack.isEmpty()){
        result.append(stack.pop());
    }

    return result.reverse().toString();

}

Answer 4

public String transformation(String s) {
    char[] array = s.toCharArray();
    int slow = 0;
    for (int fast = 0; fast < array.length; fast++) {
        if (slow == 0) {
            array[slow++] = array[fast];
        } else if (array[fast] == 'B' && array[slow - 1] == 'A' || array[fast] == 'D' && array[slow - 1] == 'C' ||
                array[fast] == 'A' && array[slow - 1] == 'B' || array[fast] == 'C' && array[slow - 1] == 'D') {
            slow--;
        } else {
            array[slow++] = array[fast];
        }
    }
    return s.substring(0, slow);
}

Answer 5

I made a recursion solution:

 

public class AbcsSwaps {

    List<String> listOfPossibilities = List.of("AB", "BA", "CD", "DC");

    public String solution(String s) {
        if (s == null || s.length() == 0) return "";
        if (s.length() == 1) return s;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (i + 2 <= s.length()) {
                String currString = s.substring(i, i + 2);
                if (listOfPossibilities.stream().anyMatch(currString::equals)) {
                    String nextString = stringBuilder.append(s, 0, i).append(s.substring(i+2)).toString();
                    return helper(nextString);
                }
            }
        }
        return s;
    }

    public String helper(String s) {
        if (listOfPossibilities.stream().noneMatch(s::contains)) return s;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (i + 2 <= s.length()) {
                String currString = s.substring(i, i + 2);
                if (listOfPossibilities.stream().anyMatch(currString::equals)) {
                    String nextString = stringBuilder.append(s, 0, i).append(s.substring(i+2)).toString();
                    return helper(nextString);
                }
            }
        }
        return s;
    }
}

Answer 6

private static String transform(String S) {
        Stack<Character> stack = new Stack<>();
        for(int i = S.length()-1; i >= 0; i--) {
            char ch = S.charAt(i);
            if(!stack.isEmpty()) {
                char topChar = stack.peek();
                if(topChar == 'A' && ch == 'B' || topChar == 'B' && ch == 'A' || topChar == 'C' && ch == 'D' ||
                    topChar == 'D' && ch == 'C') {
                    stack.pop();
                    continue;
                }
            }
            stack.push(ch);
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
}

Answer 7

def transform(s): # stack O(N)
    A = []
    for c in s:
        if A and A[-1] + c in ("AB", "BA", "CD", "DC"):
            A.pop()
        else:
            A += c
    return "".join(A)