substring-with-largest-variance

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

The variance of a string is defined as the largest difference between the number of occurrences of any <code>2</code> characters present in the string. Note the two characters may or may not be the same.

Given a string <code>s</code> consisting of lowercase English letters only, return the largest variance possible among all substrings of <code>s</code>.

A substring is a contiguous sequence of characters within a string.

&nbsp;
Example 1:

<pre>
Input: s = &quot;aababbb&quot;
Output: 3
Explanation:
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings &quot;a&quot;, &quot;aa&quot;, &quot;ab&quot;, &quot;abab&quot;, &quot;aababb&quot;, &quot;ba&quot;, &quot;b&quot;, &quot;bb&quot;, and &quot;bbb&quot;.
- Variance 1 for substrings &quot;aab&quot;, &quot;aba&quot;, &quot;abb&quot;, &quot;aabab&quot;, &quot;ababb&quot;, &quot;aababbb&quot;, and &quot;bab&quot;.
- Variance 2 for substrings &quot;aaba&quot;, &quot;ababbb&quot;, &quot;abbb&quot;, and &quot;babb&quot;.
- Variance 3 for substring &quot;babbb&quot;.
Since the largest possible variance is 3, we return it.
</pre>

Example 2:

<pre>
Input: s = &quot;abcde&quot;
Output: 0
Explanation:
No letter occurs more than once in s, so the variance of every substring is 0.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 104</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

largestVariance

Substring With Largest Variance

Maximum Subarray

maximum-subarray

最大子数组和

Array

Dynamic Programming

字符串的 波动&nbsp;定义为子字符串中出现次数 最多&nbsp;的字符次数与出现次数 最少&nbsp;的字符次数之差。

给你一个字符串&nbsp;<code>s</code>&nbsp;，它只包含小写英文字母。请你返回 <code>s</code>&nbsp;里所有 子字符串的&nbsp;最大波动&nbsp;值。

子字符串 是一个字符串的一段连续字符序列。

&nbsp;

示例 1：

<pre>
输入：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 。
</pre>

示例 2：

<pre>
输入：s = "abcde"
输出：0
解释：
s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 104</code></li>
	<li><code>s</code>&nbsp; 只包含小写英文字母。</li>
</ul>