Problem Statement in English

You’re given a string s consisting of lowercase English letters. A substring of s is called balanced if all characters in the substring appear the same number of times.

Return the length of the longest balanced substring of s. If there is no balanced substring, return 0.

Approach

We basically just have to brute force it.

Check all possible substrings and check if they are balanced or not. If they are balanced, update the result.

That’s pretty much it.

Solution in Python


class Solution:
    def longestBalanced(self, s: str) -> int:
        N = len(s)
        res = 0

        for i in range(N):

            hm = [0 for _ in range(26)]
            target = 0

            for j in range(i, N):
                index = ord(s[j]) - 97
                hm[index] += 1
                target = hm[index]

                for x in range(26):
                    if hm[x] == 0:
                        continue
                    if hm[x] != target:
                        break
                else:
                    res = max(res, j - i + 1)

        return res

Complexity

  • Time: $O(26 * (n ^ 2))$
    Since we have two nested loops and an inner loop to check if the current substring is balanced.

  • Space: $O(26)$
    Since we maintain a hashmap of size 26.

And we are done.