18 months ago

Abhilash Kalyanakrishnan • 300

Redundant Strings

A string is said to be redundant if it contains at most two distinct characters. For example: "abaaab" and "dddd" are redundant strings, while "abaaaca", "abed" are not. Given a string s of length n consisting of lowercase English letters, find the length of the longest redundant substring of the given string if you are allowed to change at most k characters of the string to any other lowercase English letter.

Example:

Consider s = "ababkbce" and k = 2. The string s can be changed to "ababbeb", which has a redundant substring "bebeb" of length 5. It can also be
changed to "abababbe", which has "abababb" (length 7) as a substring, which is a redundant string.

The length of the longest possible redundant substring is 7, so the output should be 7.

Function Description

Complete the function

getLongestRedundantSubstringLen in the editor below.
getLongestRedundantSubstringLen has the following parameter(s):

s: a string
k: an integer

Returns

int: the length of the longest redundant substring possible after at most k changes.
Constraints

• 1 ≤ n ≤ 10⁵
• 0 ≤ k ≤ n

The string s consist of lowercase English letters only

STDIN                 Function

abbac    --->       s = "abbac"

1        --->       k = 1


Sample Ouput 

5

Explanation

last character c can be changed to b, which make the string have a substring "abbab" of ith 5, which is redundant (having at max two disinct characters).

STDIN                 Function

bczeedbaaac    --->       s = "abczeedbaaac"

4       --->       k = 4


Sample Output 

9

Explanation

The 4th character ('z'), 7th character ('d'), 8th character('b'), 12th character ('c') can be changed to 'e', making the string "abceeeeeaaae", which has a redundant substring of length 9 ("eeeeeaaae")

Javed Joffrey is organizing the Stepping Stones event at Takeshi's Castle. Candidates appearing at the event need to cross a river which has 'N' stepping stones in it. Stepping on the ith stone will fetch the candidate 'P' points. The challenge isn't in crossing
the river as candidates can swim from one end to the other without stepping on any of the stones at all; it is in collecting the optimal number of points. To test the candidates' IQ, Javed introduces the condition that a candidate can't jump on 2 stones
which are <= 'M' steps away. Neither can a candidate jump backwards. To keep the event diversified, Javed will select performers from all across the board. For that he needs you to tell him the range of total
points that can be accumulated by candidates. You have to complete the function stepping_stones below which takes an integer array of size N representing the points associated with each of the N stones, and an integer denoting the value of M.

Input Format

First line contains an integer N, the number of stones. The subsequent lines contain points associated with each of the N stones (in order). The last line contains the value of M.

Constraints

• 1 ≤ N ≤ 10⁵
• -10⁹ ≤ P_i ≤ 10⁹
• 0 ≤ M ≤ 10⁶

Output Format

Return a long value denoting the range of total points the candidates can score. Range will be the possible. difference between maximum and minimum score

Sample Input 1

5
-1
-2
1
3
7
1

Sample Output 1

10

Explanation

N = 5, Points=(-1, -2, 1, 3, 7) , M= 1;
Maximum score can be attained by stepping on the 3^rd stone (1 point) and 5th stone (7 points) to get a total score of 8 points.
Minimum score will be attained by stepping on the and stone to get a total score of -2 points. Therefore, range of possible scores: 8 - (-2) = 10 points.

Sample Input 2

10
1
2
3
4
5
6
7
8
9
9
9

Sample output 2

9

Explanation

N = 10, Points= {1, 2, 3, 4, 5, 6 ,7, 8, 9, 9}, M = 9;
Maximum score can be attained by stepping on the 9th or 10th stone to get a total score of 9 points.
Minimum score will be attained by not stepping on any of the stones, and instead swimming across the points. river all the way through, to get a total score of 0
Therefore, range of possible scores: 9 - 0 = 9 points.

Sample Input 3

10
4
8
-6
-2
5
-8
-4
-8
-3
10
7

Sample Output 3

26

Explanation

Maximum score can be attained by stepping on the 2nd stone (8 points) and 10th stone (10 points), to get total score of 18 points. Minimum score will be attained by stepping on the 6 th stone to get a total score of -8 points.
Therefore, range of possible scores: 18 - (-8) = 26 points.

3 months ago

Sahil Kumar • 260

Gurugram

Here is answer for 1st question redundant string. Try all possible pairs. TC:(26*26*n) Can easily pass time limit

//Code

int main() {
     string s; int k;
    cin>>s>>k;
     int res=0;
    for (char ch='a';ch<='z';ch++) {
        
        for (char ch2='a';ch2<='z';ch2++) {
            
            
            int j=0,ans=0,op=0;
            for (int i=0;i<s.size();i++) {
                
                if (s[i]!=ch && s[i]!=ch2) {
                    op++;
                    
                }
                while ( op>k) {
                    if (s[j]!=ch && s[j]!=ch2) {
                        op--;
                    }
                    j++;
                }
                ans=max(ans ,i-j+1);
            }
            res=max(res,ans);
        }
    }
    cout<<res<<endl;
}