Make the consecutive characters distinct by using given operation

Given a cyclic connected String S (Cyclic string means start and end are connected with each other) containing characters only ‘R’ and ‘G’. the task is to return YES or NO if it is possible to make all the consecutive characters different or not by making 2 cuts in the S, which will divide the string into two pieces, then reverse one of these pieces and tie the endpoints of both strings.

Examples:

Input: S = “RGRGRG”
Output: YES
Explanation: In the given string all the adjacent characters are already different. 

Input: S = “GRGGRR”
Output: YES
Explanation: The operation is performed as:

• Make two cuts between index 3, 4 and 5, 6, So the S divides into two parts:

Graphical explanation of test case 2

• Reverse the “GR” piece of the string and merge it into the same place.

Now it can be verified that the string has all possible adjacent characters that are different including the first and last characters, They are also adjacent.

Approach: Implement the idea below to solve the problem:

If there are more than 2 pairs of the same adjacent characters or the count of R and G characters is different then the answer is NO else answer is YES. 

Steps were taken to solve the problem:

• Declare an integer N and initialize it equal to the S.length(), for holding String’s length.
• Declare and initialize two integers G and R to 0.
• Run a loop from i=0 to less than N and follow the below-mentioned steps:
  • If ( S.charAt(i) == S.charAt((i+1)) )
    • If(S.charAt(i) == ‘G’) then G++ else R++
• if ((g == 1 && r == 1) || (g == 0 && r == 0)) then output YES else NO.       

Below is the code to implement the approach:

Time Complexity: O(N)
Auxiliary Space : O(1)

Related Articles:

Given a cyclic connected String S (Cyclic string means start and end are connected with each other) containing characters only ‘R’ and ‘G’. the task is to return YES or NO if it is possible to make all the consecutive characters different or not by making 2 cuts in the S, which will divide the string into two pieces, then reverse one of these pieces and tie the endpoints of both strings.

Examples:

Input: S = “RGRGRG”
Output: YES
Explanation: In the given string all the adjacent characters are already different. 

Input: S = “GRGGRR”
Output: YES
Explanation: The operation is performed as:

• Make two cuts between index 3, 4 and 5, 6, So the S divides into two parts:

Graphical explanation of test case 2

• Reverse the “GR” piece of the string and merge it into the same place.

Now it can be verified that the string has all possible adjacent characters that are different including the first and last characters, They are also adjacent.

Approach: Implement the idea below to solve the problem:

If there are more than 2 pairs of the same adjacent characters or the count of R and G characters is different then the answer is NO else answer is YES. 

Steps were taken to solve the problem:

• Declare an integer N and initialize it equal to the S.length(), for holding String’s length.
• Declare and initialize two integers G and R to 0.
• Run a loop from i=0 to less than N and follow the below-mentioned steps:
  • If ( S.charAt(i) == S.charAt((i+1)) )
    • If(S.charAt(i) == ‘G’) then G++ else R++
• if ((g == 1 && r == 1) || (g == 0 && r == 0)) then output YES else NO.       

Below is the code to implement the approach:

Time Complexity: O(N)
Auxiliary Space : O(1)

Related Articles: