Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 9

Description

Substring With Largest Variance

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 <= 104
• s consists of lowercase English letters.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  int solve(const string &s, int i, int j) {
    int c1 = 0;
    int c2 = 0;
    int result = 0;
    for(auto c : s) {
      if(c == i) {
        c1 += 1;
      } else if (c == j) {
        c2 += 1;
      }
      if(c1 < c2) {
        c1 = 0;
        c2 = 0;
      }
      if(c1 > c2 && c2) {
        result = max(result, c1 - c2);
      }
    }
    return result;
  }
public:
  int largestVariance(string s) {
    vector<int> cnt(26);
    for(auto &c : s) {
      c -= 'a';
      cnt[c] += 1;
    }
    string rs = s;
    reverse(s.begin(), s.end());

    int answer = 0;
    for(int i = 0; i < 26; ++i) {
      for(int j = 0; j < 26; ++j) {
        if(i == j || !cnt[i] || !cnt[j]) continue;
        answer = max(answer, solve(s, i, j));
        answer = max(answer, solve(rs, i, j));
      }
    }

    return answer;
  }
};

// Accepted
// 138/138 cases passed (333 ms)
// Your runtime beats 25.79 % of cpp submissions
// Your memory usage beats 28.93 % of cpp submissions (7 MB)