diff options
Diffstat (limited to 'substr_largest_variance.cpp')
-rw-r--r-- | substr_largest_variance.cpp | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/substr_largest_variance.cpp b/substr_largest_variance.cpp new file mode 100644 index 0000000..6df445c --- /dev/null +++ b/substr_largest_variance.cpp @@ -0,0 +1,48 @@ +// 2272. Substring With Largest Variance +#include "leetcode.h" + +/* + * the variance of a string is defined as the largest difference between the + * number of ocurrences 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 's'. a substring is a contiguous sequence of characters witin + * a string. + */ + +class Solution { +public: + int largestVariance(string s) { + vector<int> arr(26); + for (auto i : s) + arr[i - 'a']++; + int ans = 0; + for (char i = 'a'; i <= 'z'; i++) { + for (char j = 'a'; j <= 'z'; j++) { + if (j == i || !arr[i - 'a'] || !arr[j - 'a']) + continue; + for (int k = 1; k <= 2; k++) { + int a1 = 0, a2 = 0; + for (auto l : s) { + if (l == i) + a1++; + if (l == j) + a2++; + if (a2 > a1) + a1 = 0, a2 = 0; + if (a1 && a2) + ans = max(ans, a1 - a2); + } + reverse(s.begin(), s.end()); + } + } + } + return ans; + } +}; + +int main() { + Solution obj; + printf("%d\n", obj.largestVariance("aababbb")); // expect: 3 + printf("%d\n", obj.largestVariance("abcde")); // expect: 0 +}; |