Leetcode-2272. Substring With Largest Variance [C++][Java]

[Leetcode-2272. Substring With Largest Variancehttps://leetcode.com/problems/substring-with-largest- variance/description/]( variance/description/ “Leetcode-2272. Substring With Largest Variance”)[2272 最大波动的子字符串 - 力扣（LeetCode）2272 最大波动的子字符串 - 字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。子字符串 是一个字符串的一段连续字符序列。 示例 1：输入：s = “aababbb"输出：3解释：所有可能的波动值和它们对应的子字符串如以下所示：- 波动值为 0 的子字符串：“a” ，“aa” ，“ab” ，“abab” ，“aababb” ，“ba” ，“b” ，“bb” 和 “bbb” 。- 波动值为 1 的子字符串：“aab” ，“aba” ，“abb” ，“aabab” ，“ababb” ，“aababbb” 和 “bab” 。- 波动值为 2 的子字符串：“aaba” ，“ababbb” ，“abbb” 和 “babb” 。- 波动值为 3 的子字符串 “babbb” 。所以，最大可能波动值为 3 。示例 2：输入：s = “abcde"输出：0解释：s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。 提示： * 1 <= s.length <= 104 * s 只包含小写英文字母。https://leetcode.cn/problems/substring-with-largest- variance/description/]( variance/description/ “2272. 最大波动的子字符串 - 力扣（LeetCode）”)

一、题目描述

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 thelargest 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.

二、解题思路

• 时间复杂度：O(n * 26)
• 空间复杂度：O(1)

【C++】

class Solution { public: int largestVariance(string s) { int f0[26][26]{}, f1[26][26]; memset(f1, -0x3f, sizeof(f1)); int res = 0; for (auto& ch : s) { int a = ch - ‘a’; for (int b = 0; b < 26; ++b) { if (a == b) {continue;} f0[a][b] = max(f0[a][b], 0) + 1; // a为主频次（允许不含b）时的频次差 f1[a][b]++; // a为主频次时的频次差，含b时有效；不含b时为很小的负数值 f1[b][a] = f0[b][a] = max(f0[b][a], 0) - 1; // b为主频次（这里一定含a）时的频次差 res = max(max(res, f1[a][b]), f1[b][a]); } } return res; } };

【Java】

class Solution { public int largestVariance(String s) { int f0[][] = new int[26][26], f1[][] = new int[26][26]; for (int[] row : f1) {Arrays.fill(row, Integer.MIN_VALUE);} int res = 0; for (char ch : s.toCharArray()) { int a = ch - ‘a’; for (int b = 0; b < 26; ++b) { if (a == b) {continue;} f0[a][b] = Math.max(f0[a][b], 0) + 1; f1[a][b]++; f1[b][a] = f0[b][a] = Math.max(f0[b][a], 0) - 1; res = Math.max(Math.max(res, f1[a][b]), f1[b][a]); } } return res; } }