Write functional code for solving the problem given below

1.	Write functional code for solving the problem given below
Answer» "You have been GIVEN the string s (which consists of only uppercase English characters) and the integer k. You can replace any character in the string with ANOTHER uppercase English character. This operation can be performed at most k times. After executing the preceding procedures, RETURN the length of the longest substring containing the same letter." Sample input and output is shown below: Input: s = "AABABBA", k = 1 Output: 4 C ++ function which solves the given Data Structures and Algorithm problem is given below: int replaceCharacters(string s, int k) { int n = s.length(); int maxLength = 0, maxFreq = 0, l = 0; vector<int> freq(26); for(int r = 0; r < n; r ++){ int ascii = s[r] - 'A'; freq[ascii] ++; maxFreq = max(maxFreq, freq[ascii]); while(r - l + 1 - maxFreq > k){ freq[s[l] - 'A'] --; l ++; } maxLength = max(maxLength, r - l + 1); } return maxLength; } In this question, we use the sliding window technique along with two pointers "l" and "r" to get our answer. We keep moving the pointer "r" by one from left to right each iteration and update the frequency of all characters in the window starting from index l to r. If the difference of the subarray length l to r and maximum frequency among all the characters in the window of l to r is greater than the given VALUE k, we move l forward until the same condition does not hold (l's value is incremented hence subarray length, that is, the value of "r - l + 1" keeps decreasing). In the end, we update our answer variable with the value of the length of the subarray "r - l + 1" since we can guarantee that after performing at most k op, all characters in the subarray can be made the same.

Answer»

"You have been GIVEN the string s (which consists of only uppercase English characters) and the integer k. You can replace any character in the string with ANOTHER uppercase English character. This operation can be performed at most k times. After executing the preceding procedures, RETURN the length of the longest substring containing the same letter."

Sample input and output is shown below:

Input: s = "AABABBA", k = 1
Output: 4

C ++ function which solves the given Data Structures and Algorithm problem is given below:

int replaceCharacters(string s, int k) { int n = s.length(); int maxLength = 0, maxFreq = 0, l = 0; vector<int> freq(26); for(int r = 0; r < n; r ++){ int ascii = s[r] - 'A'; freq[ascii] ++; maxFreq = max(maxFreq, freq[ascii]); while(r - l + 1 - maxFreq > k){ freq[s[l] - 'A'] --; l ++; } maxLength = max(maxLength, r - l + 1); } return maxLength; }

In this question, we use the sliding window technique along with two pointers "l" and "r" to get our answer. We keep moving the pointer "r" by one from left to right each iteration and update the frequency of all characters in the window starting from index l to r. If the difference of the subarray length l to r and maximum frequency among all the characters in the window of l to r is greater than the given VALUE k, we move l forward until the same condition does not hold (l's value is incremented hence subarray length, that is, the value of "r - l + 1" keeps decreasing). In the end, we update our answer variable with the value of the length of the subarray "r - l + 1" since we can guarantee that after performing at most k op, all characters in the subarray can be made the same.

Write functional code for solving the problem given below

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment