Substring With Largest Variance - Try Each Pair of Characters [JS]
Description Solution: Try Each Pair of Characters When we only have two unique characters, we can find the largest difference in O(n) time using kadane's algorithm. Since s consists of lowercase letters only, there are only at most 26 * 26 different pairs. We can try each pair of characters. To recap kadane's algorithm: Keep an ongoing sum, when it becomes negative reset it to the current number -> take max(sum + curr, curr) One catch is that the substring must contain both of the characters, so we need to account for the case where the substring only consists of one character. We can do this by keeping track of whether the other character existed before, and can 'virtually' add it back when we need it. e.g: "abbb", where we need the "a" in front of the 3 b's. Time Complexity: O(26^2 * n) 1286ms Space Complexity: O(n) 44.4MB var largestVariance = function ( s ) { let chars = new Set (s.split( "" )), maxDiff = 0 ; fo...