Maximum Number of Xs.

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
0 upvote
Asked in company
Cultfit

Problem statement

You are given a string ‘S’ of length ‘N’. The string ‘S’ consists of only two characters ‘X’ and ‘Y’. In one operation, you can select two indices ‘i’ and ‘j’, and flip each character of the substring from ‘i’ to ‘j’. Flip the characters means changing the character ‘X’ to ‘Y’ and the character ‘Y’ to ‘X’.

You need to perform exactly one operation. Find the maximum number of ‘X’s in the string ‘S’ that you can get after performing the operation.

Example: 
Input: ‘N’ = 4,  ‘S’ = “XYYX”

Output: 4.

Select ‘i’ = 1 and ‘j’ = 2. Flip all the characters of the substring from 1 to 2, and we get ‘S’ = ‘XXXX’. Hence, the number of ‘X’s is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the string ‘S’. 

The second line of each test case contains an arbitrary string ‘S’.
Output format : 
For each test case, you don’t need to print anything just return the maximum number ‘X’s you can get after performing exactly one operation.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^6

Sum of N Over all the Test cases <= 10^6

Time Limit: 1 sec
Sample Input 1 :
2
5
YYXYX
3
XXY
Sample Output 1 :
4
3
Explanation Of Sample Input 1 :
For the first case:
Select ‘i’ = 0 and ‘j’ = 3. Flip all the characters of the substring from 0 to 3, and we get ‘S’ = ‘XXYXX’. Hence, the number of ‘X’s is 4.


For the second case:
Select ‘i’ = 2 and ‘j’ = 2. Flip all the characters of the substring from 2 to 2, and we get ‘S’ = ‘XXX’. Hence, the number of ‘X’s is 3.
Sample Input 2 :
2
8
XYYYXYYY
5
YYXXY
Sample Output 2 :
7
4
Hint

Can you think of a way to generate all possible valid combinations of ‘i’ and ‘j’ and calculate the value?

Approaches (2)
BruteForce

In this approach, We need to find a substring that when flipped contributes a maximum number of ‘X’ to the whole string. We can run two nested for loops to get all possible substrings then for each substring we can calculate how many ‘X’ that substring will contribute when it will be flipped.


 

The steps are as follows:-

function getMaxX(string s):

  1. Initialize a variable 'ANS' with a value 0.
  2. Run a loop from 'i' = 0 to 'N' - 1:
    • Initialize variables 'X',  'LEFT' and ‘RIGHT’ with value 0.
    • Run a loop from 'k' = 0 to 'i' - 1:
      • If the value of 'S' at 'k' is 'X' then increment 'LEFT' by 1.
    • Run a loop from 'k' = i to 'N' - 1:
      • If the value of 'S' at 'k' is 'X' then increment 'RIGHT' by 1.
    • Run a loop from 'j' = 'i' to 'N' - 1:
      • If the value of 'S' at 'j' is not 'X' then increment 'X' by 1.
      • Else decrement 'RIGHT' by 1.
      • Update the value of 'ANS' with the maximum value of 'ANS' and 'LEFT' + 'X' + 'RIGHT'.
  3. Return the value of 'ANS'
Time Complexity

O( N^2 ), Where ‘N’ is the length of the string ‘S’.

 

We are exploring all possible valid combinations of ‘i’ and ‘j’ by running two nested loops.

Hence the time complexity is O( N^2 ).

Space Complexity

O( 1 ),  

 

We are not using any extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Maximum Number of Xs.
Full screen
Console