Quick Overview

Given a string of lowercase letters, find the length of the longest substring in which every letter that appears occurs the same number of times. It tests substring enumeration with incremental frequency tracking and a precise definition of what counts as balanced.

Longest Substring in Which Every Present Letter Occurs Equally Often

Company: DRW

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

A string is **balanced** if every letter that occurs in it occurs the same number of times. For example, `"aabb"`, `"abc"` and `"zzz"` are balanced, while `"aab"` is not. Given a string of lowercase English letters, return the length of its longest balanced substring. ### Function Signature ```python def longest_balanced_substring(s: str) -> int: ``` ### Rules - A substring is a contiguous, non-empty part of `s`. - Only the letters that occur in the substring are compared; letters that do not occur in it are ignored. A substring made of one repeated letter is therefore balanced. - Every single character is a balanced substring, so the answer is at least `1`. ### Constraints - `1 <= len(s) <= 1000` - `s` consists only of lowercase English letters `a` to `z`. ### Examples **Example 1** ```text Input: s = "aabbc" Output: 4 ``` `"aabb"` contains `a` twice and `b` twice. The only longer substring is the whole string, in which `c` occurs once while `a` and `b` occur twice. **Example 2** ```text Input: s = "aaab" Output: 3 ``` The whole string has three `a` and one `b`, so it is not balanced. `"aaa"` contains only `a`, so it is balanced. **Example 3** ```text Input: s = "xyzzyxx" Output: 6 ``` Both `"xyzzyx"` and `"yzzyxx"` contain each of `x`, `y` and `z` exactly twice. The whole string contains `x` three times, so it is not balanced.

Overview: Given a string of lowercase letters, find the length of the longest substring in which every letter that appears occurs the same number of times. It tests substring enumeration with incremental frequency tracking and a precise definition of what counts as balanced.

Read the full DRW Software Engineer interview experience this question came from

A string is **balanced** if every letter that occurs in it occurs the same number of times. For example, `"aabb"`, `"abc"` and `"zzz"` are balanced, while `"aab"` is not. Given a string `s` of lowercase English letters, return the length of its longest balanced substring. ### Rules - A substring is a contiguous, non-empty part of `s`. - Only the letters that occur in the substring are compared; letters that do not occur in it are ignored. A substring made of one repeated letter is therefore balanced. - Every single character is a balanced substring, so the answer is at least `1`. - The result is a single length between `1` and `len(s)`, so it is unique. It never exceeds 1000 and fits in a 32-bit integer. ### Constraints - `1 <= len(s) <= 1000` - `s` consists only of lowercase English letters `a` to `z`. ### Examples **Example 1** ```text Input: s = "aabbc" Output: 4 ``` `"aabb"` contains `a` twice and `b` twice. The only longer substring is the whole string, in which `c` occurs once while `a` and `b` occur twice. **Example 2** ```text Input: s = "aaab" Output: 3 ``` The whole string has three `a` and one `b`, so it is not balanced. `"aaa"` contains only `a`, so it is balanced.

Constraints

  • 1 <= len(s) <= 1000
  • s consists only of lowercase English letters 'a' to 'z'.

Examples

Input: ('a',)

Expected Output: 1

Explanation: Minimum valid input: a single character is balanced.

Input: ('ab',)

Expected Output: 2

Explanation: Two distinct letters once each: the whole string is balanced.

Hints

  1. Only letters that actually occur in a substring are compared, so a run of one repeated letter is always balanced and every single character gives an answer of at least 1.
  2. Balance is not monotonic: "aab" is unbalanced but extending it to "aabb" makes it balanced again, so an unbalanced substring can still grow into a balanced one.
  3. The string has at most 1000 characters, so examining many substrings is affordable as long as you do not recount each one from scratch.

Loading coding console...

Show the approach

Approach

Characterization: let a substring have length L, d distinct letters, and let m be the largest count of any letter in it. The d counts sum to L and each is at most m, so L <= d * m, with equality exactly when every occurring letter appears m times, i.e. exactly when the substring is balanced. Letters absent from the substring never contribute to d or m, which matches the rule that they are ignored.

Algorithm: for each start index i, extend the end index j one character at a time while maintaining the 26 letter counts, d (incremented when a count goes from 0 to 1) and m (counts only grow while the window extends, so m = max(m, new count)). Each extension is O(1), and s[i..j] is balanced iff d * m == j - i + 1; record the largest such length.

Correctness: every non-empty substring s[i..j] is tested, except those skipped by the pruning rule: once the remaining suffix length n - i is no longer than the best length found, no substring starting at i or later can beat it, so the scan stops. Balance is not monotonic in j ("aab" is unbalanced but "aabb" is balanced), so the inner loop never stops at the first unbalanced window.

Edge cases: a single character gives d = 1, m = 1, L = 1, so the answer is at least 1; a string of one repeated letter returns len(s); a string where all letters occur equally returns len(s). The answer is at most 1000 and d * m is at most 26 * 1000, so 32-bit integers suffice in every language.

Time complexity:
O(n^2)
Space complexity:
O(n)