Longest Repeating Character Replacement || NEETCODE 150

Longest Repeating Character Replacement || NEETCODE 150

Join Us -

Timestamps:
0:00 - 1:20 : Introduction
1:21 - 4:46 : Question discussed
4:47 - 13:46 : Discussion of brute force approach (Thinking it loud)
13:47 - 19:02: Discussion of optimised approach

Code link :

#leetcode #coding #programming #coding #interview #programmer #tech #software #leetcode #newyear #january #leetcodechallenge #binarysearch #placement #greedy

[ayushlingayat]

Time Complexity of Brute Force Approach is 0(n^3) and Space Complexity is 0(n)

[prathamgoel]

class Solution {
public int characterReplacement(String s, int k) {
int max = 0;
int res = 0;
int[] arr = new int[26];
int i = 0;
int j = 0;
while (j < s.length()) {
arr[s.charAt(j) - 'A']++;
max = Math.max(max, arr[s.charAt(j) - 'A']);
if (j - i + 1 - max > k) {
arr[s.charAt(i) - 'A']--;
i++;
}
res = Math.max(res, j - i + 1);
j++;
}
return res;
}
}

[prathamgoel]

Time Complexity of Brute force approach is O(n^2).

[gomzysharma]

1>1 is true? It's false 17:18, she just copy, pasted the solution + very bad variable name choosen.

[Aayush-hogl]

i think you have just pasted up the optimised solution, you don't have proper understanding of solution, why it is working

[prathamgoel]

Brute Force Approach

class Solution {
private boolean isValid(String s, int k) {
int[] arr = new int[26];
int max = 0;
for (char c : s.toCharArray()) {
arr[c - 'A']++;
max = Math.max(max, arr[c - 'A']);
}
return (s.length() - max) <= k;
}

public int characterReplacement(String s, int k) {
int maxlen = 0;
for (int start = 0; start < s.length(); start++) {
int end = start;
StringBuilder sb = new StringBuilder();
while (end < s.length()) {
sb.append(s.charAt(end));
if (!isValid(sb.toString(), k)) {
break;
}
maxlen = Math.max(maxlen, sb.length());
end++;
}
}
return maxlen;
}
}