4055. Longest Balanced Substring I¶
4055. Longest Balanced Substring I
Medium
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 <= 1000sconsists of lowercase English letters.
Solution¶
class Solution {
public int longestBalanced(String s) {
int n = s.length();
int res = 0;
for (int i = 0; i < n; i++) {
int freq[] = new int[26];
for (int j = i; j < n; j++) {
freq[s.charAt(j) - 'a']++;
int flag = 1;
int maxi = 0;
for (int ele : freq)
maxi = Math.max(maxi, ele);
for (int ele : freq) {
if (ele > 0 && ele != maxi)
flag = 0;
}
if (flag == 1)
res = Math.max(res, j - i + 1);
}
}
return res;
}
}
Complexity Analysis¶
- Time Complexity: O(?)
- Space Complexity: O(?)
Explanation¶
[Add detailed explanation here]