PROBLEM LINK:
Author: tseccodecell
DIFFICULTY:
Medium
PROBLEM:
Given a string S the consist of only characters ‘R’ and ‘K’.
You need to choose two indices i and j (within the string length) and flip all the characters between those positions. A filp means if S[i]=‘R’ you change it to ‘K’ and if S[i]=‘K’ you change it to ‘R’.
EXPLANATION:
If sum be the total number of Rs. Initially, S is some constant value, and then we flip a part of the array. On flipping a ‘K’, the sum increases by 1 and on flipping a R, sum decreases by 1. Hence we can save Rs as -1 and K as +1. Now we must find a Largest Sum Contiguous Subarray out of this. An O(n) algorithm is explained here. Once we have the maximum sum, that is the number of extra Rs that are generated after a flip. We can add this to inital no of Rs to get our answer.