Last Updated: 28 Jul, 2022

Maximum Number of Xs.

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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):

Initialize a variable 'ANS' with a value 0.
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'.
Return the value of 'ANS'

Solve now

02 Approach

In this approach, the idea is to substitute the value of ‘X’ with -1 and the value of ‘Y’ with 1. Now this problem is transformed into well known problem “Finding subarray with mamxium sum”. To get the subarray with maximum sum we can iterate over all the elements and add its value to the variable ‘SUM’ and then update the maximum sum. If ‘SUM’ < 0 then we update the value of ‘SUM’ to 0.

We can find the starting and ending index of the subarray with maximum sum by modifying the Kadane Algorithm a little bit. Then we run a loop from 0 to the starting index -1 of the subarray and then count the number of ‘X’, then we iterate over the subarray from starting index to the ending index and count the number of ‘Y’ (since it will be flipped to ‘X’) and finally we iterate from ending index + 1 to the last character of the string and count the number of ‘X’. The final answer will be the sum of all the counts.

The steps are as follows:-

function getMaxX(string s):

Initialize variables 'SUM', 'leftIdx' 'rightIdx' with value 0.
Initialize variables 'LEFT', 'RIGHT' with value 0.
Initialize variables 'mxLen' with value -10^8 and 'ANS' with value 0.
Run a loop from 'i' = 0 to 'N' - 1:
- If value of 'S' at i is 'X' then decrement 'SUM' by 1.
- Else increment 'SUM' by 1.
- If value of 'mxLen' < 'SUM':
  - Modify the value of 'mxLen' to the value of 'SUM'.
  - Modify the variable 'RIGHTIDX' to the value of 'i'.
  - Modify the variable 'LEFT' to the value of 'LEFTIDX'.
  - Modify the value of 'RIGHT' to the value of 'RIGHTIDX'.
- If the value of 'SUM' is less than 0:
  - Modify the value of 'SUM' to 0.
  - Modify the value of 'leftIdx' to 'i' + 1.
  - Modify the value of 'rightIdx' to 'i' + 1.
Run a loop from 'i' = 0 to 'LEFT' - 1:
- If value of 'S' at 'i' is 'X' then increment the value of ans by 1.
Run a loop from 'i' = 'LEFT' to 'RIGHT':
- If value of 'S' at 'i' is 'Y' then increment the value of ans by 1.
Run a loop from 'i' = 'RIGHT' + 1 to 'N' - 1:
- If value of 'S' at 'i' is 'X' then increment the value of ans by 1.
Return the value of 'ANS'.

Solve now