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 <= 104s consists of lowercase English letters.This approach leverages a modified version of Kadane's algorithm to find the largest variance by calculating frequency differences for each character pair combination. We'll use a variation of Kadane's approach to track the balance difference in frequencies between two characters across the string.
The solution involves iterating over all possible pairs of characters (a, b). For each pair, we calculate the difference in frequency counts using a variation of Kadane's algorithm approach to determine the maximum variance for that pair. The balance is reset when frequency of 'b' exceeds 'a', avoiding any negative variance.
C++
Java
Python
C#
JavaScript
The time complexity is O(26^2 * n) = O(n), where n is the length of the string, due to iterating over each character pair and traversing the string. The space complexity is O(1) because we use only a fixed amount of extra space.
The second approach is using the sliding window technique, which dynamically adjusts the window as we scan through the string. This helps to efficiently find all possible maximum variances for character combinations by maintaining two counters and extending or shrinking the window as needed.
In this C solution using the sliding window technique, we maintain a dynamic window while iterating over the string. The window adjusts dynamically to keep the variance optimal, expanding and contracting based on character balance.
C++
Java
Python
C#
JavaScript
Time complexity is O(n) due to efficient window management, spanning the string with a single pass, and space complexity veins at O(1) for predictable and limited use.
| Approach | Complexity |
|---|---|
| Kadane's Algorithm for Character Pair | The time complexity is O(26^2 * n) = O(n), where n is the length of the string, due to iterating over each character pair and traversing the string. The space complexity is O(1) because we use only a fixed amount of extra space. |
| Sliding Window Technique | Time complexity is O(n) due to efficient window management, spanning the string with a single pass, and space complexity veins at O(1) for predictable and limited use. |
Substring With Largest Variance | 2272 LeetCode | Maths | Leetcode Biweekly Contest 78 • CodeWithSunny • 12,669 views views
Watch 9 more video solutions →Practice Substring With Largest Variance with our built-in code editor and test cases.
Practice on FleetCode