Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Substring With Largest Variance LeetCode Solution
Problem – Substring With Largest Variance LeetCode Solution
The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same.
Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "aababbb"
Output: 3
Explanation:
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings "a", "aa", "ab", "abab", "aababb", "ba", "b", "bb", and "bbb".
- Variance 1 for substrings "aab", "aba", "abb", "aabab", "ababb", "aababbb", and "bab".
- Variance 2 for substrings "aaba", "ababbb", "abbb", and "babb".
- Variance 3 for substring "babbb".
Since the largest possible variance is 3, we return it.
Example 2:
Input: s = "abcde"
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Substring With Largest Variance LeetCode Solution in C++
int largestVariance(string s) {
int res = 0;
unordered_set<char> unique(begin(s), end(s));
for (char a : unique)
for (char b : unique) {
int var = 0, has_b = 0, first_b = 0;
for (auto ch : s) {
var += ch == a;
if (ch == b) {
has_b = true;
if (first_b && var >= 0)
first_b = false;
else if (--var < 0) {
first_b = true;
var = -1;
}
}
res = max(res, has_b ? var : 0);
}
}
return res;
}
Substring With Largest Variance LeetCode Solution in Java
class Solution {
public int largestVariance(String s) {
int [] freq = new int[26];
for(int i = 0 ; i < s.length() ; i++)
freq[(int)(s.charAt(i) - 'a')]++;
int maxVariance = 0;
for(int a = 0 ; a < 26 ; a++){
for(int b = 0 ; b < 26 ; b++){
int remainingA = freq[a];
int remainingB = freq[b];
if(a == b || remainingA == 0 || remainingB == 0) continue;
// run kadanes on each possible character pairs (A & B)
int currBFreq = 0, currAFreq = 0;
for(int i = 0 ; i < s.length() ; i++){
int c = (int)(s.charAt(i) - 'a');
if(c == b) currBFreq++;
if(c == a) {
currAFreq++;
remainingA--;
}
if(currAFreq > 0)
maxVariance = Math.max(maxVariance, currBFreq - currAFreq);
if(currBFreq < currAFreq && remainingA >= 1){
currBFreq = 0;
currAFreq = 0;
}
}
}
}
return maxVariance;
}
}
Substring With Largest Variance LeetCode Solution in Python
class Solution:
def largestVariance(self, s: str) -> int:
res = 0
chars = list(set(s))
# Loop through each pari of (c1, c2)
for i in range(len(chars)):
for j in range(i+1, len(chars)):
c1, c2 = chars[i], chars[j]
# keep track of count(c1) - count(c2)
diff = 0
# max and min of diff
# result should be maximum of (diff - min_diff, max_diff - diff)
# e.g. "baabaa", at index = 0, min_diff = -1. when index = 5, diff = 4 - 2 = 2, result = diff - min_diff = 2 - (-1) = 3
max_diff = min_diff = 0
# diff at the previous occurance of c1/c2
last_c1_diff = last_c2_diff = 0
# check wether we have met c1/c2 during the loop
meet_c1 = meet_c2 = False
for c in s:
if c == c1:
meet_c1 = True
diff += 1
# use last_c1_diff instead of diff because we have to make sure that c1 is in the rest part of the substring.
# e.g. [c1, c1, c2, c2, c2]
# At index = 1, if we use diff = 2 -> max_diff = 2
# At index = 4, diff = 2 - 3 = -1, result = max_diff - diff = 3.
# Though we have [c2, c2, c2] as a substring, c1 is not in this string and the result is invalid
max_diff = max(last_c1_diff, max_diff)
last_c1_diff = diff
elif c == c2:
meet_c2 = True
diff -= 1
min_diff = min(last_c2_diff, min_diff)
last_c2_diff = diff
else:
continue
# update the result only when we have met both c1 and c2
if meet_c1 and meet_c2:
res = max(diff - min_diff, max_diff - diff, res)
return res
Substring With Largest Variance LeetCode Solution Review:
In our experience, we suggest you solve this Substring With Largest Variance and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Substring With Largest Variance LeetCode Solution
Conclusion:
I hope this Substring With Largest Variance LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
