Code Destine

Problem Statement

You have given a valid string V = “abc”, you may split V into two pieces X and Y such that X + Y is equal to V (X or Y can be empty). Then, X + “abc” + Y is also valid.

If for example string S = “abc”, then examples of valid strings are: “abc”, “aabcbc”, “abcabc”, “abcabcababcc”. Examples of invalid strings are: “abccba”, “ab”, “cababc”, “bac”.

Return true if a given string S is valid otherwise returns false.

Example 

Input :- "aabcbc"
Output :- true

Input :- "abcabcababcc"
Output :- true

Input :- "abccba"
Output :- false

Solution

This problem can be solved in following steps :-

1. Create the character array from the input String S.
2. Create two variables i and k with initial value zero, i variable is used for traversing the character array and k variable is used as an index pointer for sliding window.
3. Traverse the character array from start to end using i variable. At each iteration, check if the current character is ‘c’ and sliding window contains ‘abc’ (by checking the last two characters are ‘b’ and ‘a’ receptively).
4. If the above condition is true, then make a sliding window size 0 by decreasing the value of the k variable by 2, else increase the value of k variable by 1.

Program

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		boolean result = main.isValid("abcabcababcc");
		System.out.println(result);
	}
	
	/* Solution */
	public boolean isValid(String S) {
        
        int k = 0;
        int i = 0;        
        char[] array = S.toCharArray();
        while(i < array.length){ 
            if(array[i] == 'c' && (k > 1) && array[k-1] == 'b' && array[k-2] == 'a'){
                i++;
                k = k - 2;
            }else {
                array[k] = array[i];
                i++;
                k++;
            }
        }
        return k == 0;
    }
}

Result

true

Similar Post

1. Robot Return to Origin
2. Rotated Digits
3. Ransom Note

That’s all for Check If Word Is Valid After Substitutions in Java, If you liked it, please share your thoughts in a comments section and share it with others too.