HardNo. 2272
Substring With Largest Variance — LeetCode 2272 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- s = "aababbb"
- Output
- 3
- Explanation
- All possible variances along with their respective substrings are listed below:
Python solution
class Solution:
def largestVariance(self, s: str) -> int:
ans = 0
for a, b in permutations(ascii_lowercase, 2):
if a == b:
continue
f = [0, -inf]
for c in s:
if c == a:
f[0], f[1] = f[0] + 1, f[1] + 1
elif c == b:
f[1] = max(f[1] - 1, f[0] - 1)
f[0] = 0
if ans < f[1]:
ans = f[1]
return ansComplexity
- Time
- O(n × |Σ|2), where n is the length of the string, and |Σ| is the size of the character set
- Space · auxiliary
- O(1)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2272. Substring With Largest Variance is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2267 | Check if There Is a Valid Parentheses String Path | Hard |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
| 0064 | Minimum Path Sum | Medium |
Frequently asked questions
- How hard is LeetCode 2272. Substring With Largest Variance?
LeetCode 2272. Substring With Largest Variance is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2272. Substring With Largest Variance?
The Python solution on this page runs in O(n × |Σ|2), where n is the length of the string, and |\Sigma| is the size of the character set.
- What is the space complexity of LeetCode 2272. Substring With Largest Variance?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2272. Substring With Largest Variance cover?
LeetCode 2272. Substring With Largest Variance is tagged Array and Dynamic Programming on LeetCode.