-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path3713.longest-balanced-substring-i.cpp
More file actions
73 lines (64 loc) · 1.9 KB
/
3713.longest-balanced-substring-i.cpp
File metadata and controls
73 lines (64 loc) · 1.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// Tag: Hash Table, String, Counting, Enumeration
// Time: O(N^2)
// Space: O(1)
// Ref: -
// Note: -
// You are given a string s consisting of lowercase English letters.
// A substring of s is called balanced if all distinct characters in the substring appear the same number of times.
// Return the length of the longest balanced substring of s.
//
// Example 1:
//
// Input: s = "abbac"
// Output: 4
// Explanation:
// The longest balanced substring is "abba" because both distinct characters 'a' and 'b' each appear exactly 2 times.
//
// Example 2:
//
// Input: s = "zzabccy"
// Output: 4
// Explanation:
// The longest balanced substring is "zabc" because the distinct characters 'z', 'a', 'b', and 'c' each appear exactly 1 time.
//
// Example 3:
//
// Input: s = "aba"
// Output: 2
// Explanation:
// One of the longest balanced substrings is "ab" because both distinct characters 'a' and 'b' each appear exactly 1 time. Another longest balanced substring is "ba".
//
//
// Constraints:
//
// 1 <= s.length <= 1000
// s consists of lowercase English letters.
//
//
class Solution {
public:
int longestBalanced(string s) {
int n = s.size();
int result = 0;
for (int l = 0; l < n; ++l) {
if (n - l <= result) break;
vector<int> cnt(26, 0);
int uniq = 0;
int maxfreq = 0;
for (int r = l; r < n; ++r) {
if (cnt[s[r] - 'a'] == 0) {
uniq++;
}
cnt[s[r] - 'a']++;
if (cnt[s[r] - 'a'] > maxfreq) {
maxfreq = cnt[s[r] - 'a'];
}
int cur = r - l + 1;
if (uniq * maxfreq == cur && cur > result) {
result = cur;
}
}
}
return result;
}
};