Longest Substring with At Least K Repeating Characters | Leetcode 395 | Nov2020 Day 26 Challeneg

1) 0:00 Explaining the problem out loud
2) 1:16 Algorithm walkthrough
3) 3:30 Coding it up
4) 8:22 Time Complexity

TC : O(n2)
SC : O(1)

[ax]

The second portion --- algorithm walkthrough -- is awesome. The picture helps clear things up! Thanks!

[akashsrivastava]

one of the best approach i saw for this problem

[kirankorey]

The sliding window solution is O(N) and this solution is O(N^2), but still how is this faster than the sliding window?

[goodpeople]

Clear solution !
Laptop : please charge me man
Coder : I will finish before you finish

[siddharthrawat]

Great explaination, one thing : freq[str[end]-'a']>0 isn't required, because it will always be >0, we need to take care of <k values. Right?

[srikanthvvgs]

Could you share the sliding window solution for the same problem

[anandpandey]

//Bruteforce Approach

class Solution {
public int longestSubstring(String str, int k) {
int maxLength = 0;

for (int start = 0; start < str.length(); start++) {
for (int end = start; end < str.length(); end++) {
if (isValidSubstring(str.substring(start, end + 1), k)) {
maxLength = Math.max(maxLength, end - start + 1);
}
}
}

return maxLength;
}

private boolean isValidSubstring(String str, int k) {
int[] freqArray = new int[26];

for (int i = 0; i < str.length(); i++) {
freqArray[str.charAt(i) - 'a']++;
}

for (int i = 0; i < str.length(); i++) {
if (freqArray[str.charAt(i) - 'a'] < k) {
return false;
}
}

return true;
}
}


//Improved Approach

class Solution {
public int longestSubstring(String str, int k) {
int maxLength = 0;
int[] freqArray = new int[26];

for (int start = 0; start < str.length(); start++) {
for (int end = start; end < str.length(); end++) {
freqArray[str.charAt(end) - 'a']++;
if (isValidSubstring(str.substring(start, end + 1), k, freqArray)) {
maxLength = Math.max(maxLength, end - start + 1);
}
}
Arrays.fill(freqArray, 0);
}

return maxLength;
}

private boolean isValidSubstring(String str, int k, int[] freqArray) {
for (int i = 0; i < str.length(); i++) {
if (freqArray[str.charAt(i) - 'a'] < k) {
return false;
}
}

return true;
}
}


//Good Approach

class Solution {
public int longestSubstring(String str, int k) {
int maxLength = 0;
int[] freqArray = new int[26];
StringBuilder substring = new StringBuilder();

for (int start = 0; start < str.length(); start++) {
for (int end = start; end < str.length(); end++) {
freqArray[str.charAt(end) - 'a']++;


if (isValidSubstring(substring, k, freqArray)) {
maxLength = Math.max(maxLength, end - start + 1);
}
}
substring.setLength(0);
Arrays.fill(freqArray, 0);
}

return maxLength;
}

private boolean str, int k, int[] freqArray) {
for (int i = 0; i < str.length(); i++) {
if (freqArray[str.charAt(i) - 'a'] < k) {
return false;
}
}

return true;
}
}


//Better Approach

public class Solution {
public int longestSubstring(String str, int k) {
if(str.length()<k){
return 0;
}

int[] frequencyArray = new int[26];

for (int i = 0; i < str.length(); i++) {

}

for(int i=0;i<str.length();i++){
//We use all the infrequent elements as splits

int left=longestSubstring(str.substring(0, i), k);
int right=longestSubstring(str.substring(i+1), k);
return Math.max(left, right);
}
}

//All characters in the current substring have a frequency greater than or equal to k.
return str.length();
}
}


//Further Optimised

public class Solution {
public int longestSubstring(String str, int k) {
int[] frequencyArray = new int[26];
return longestSubstringHelper(str, 0, str.length() - 1, k, frequencyArray);
}

public int longestSubstringHelper(String str, int start, int end, int k, int[] frequencyArray) {
if ((end - start + 1) < k) {
return 0;
}

Arrays.fill(frequencyArray, 0);
for (int i = start; i <= end; i++) {
frequencyArray[str.charAt(i) - 'a']++;
}

for (int i = start; i <= end; i++) {
// We use all the infrequent elements as splits
if (frequencyArray[str.charAt(i) - 'a'] < k) {
int left = longestSubstringHelper(str, start, i - 1, k, frequencyArray);
int nextIndex = i;
while (nextIndex < end && str.charAt(nextIndex) == str.charAt(i)) {
nextIndex++; // Skip consecutive infrequent characters to reduce redundant recursive calls
}
int right = longestSubstringHelper(str, nextIndex, end, k, frequencyArray);
return Math.max(left, right);
}
}

// All characters in the current substring have a frequency greater than or equal to k.
return end - start + 1;
}
}


//Optimal Approach (Sliding window)

[ax]

The code portion is too small to be seen clearly. I tried high definition, still too small. You can try zoom in a little bit next time. Great work, thanks!