JP Morgan·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

JP Morgan software engineer interview with a string problem that looks straightforward but has a few edge cases worth thinking through carefully.

Questions Asked (1)

Given a binary string of 0s and 1s, count all substrings where the number of 0s equals the number of 1s AND all the 0s are grouped together and all the 1s are grouped together (so valid substrings look like 0^k 1^k or 1^k 0^k for some k >= 1).

Algorithms & Data Structures

Author's notes

My first instinct was prefix sums for the equal-count part, but that misses the contiguous grouping constraint entirely.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and edge cases, then propose an O(n) solution by scanning the string and identifying maximal runs of identical characters. For each adjacent pair of runs, count the valid substrings that span the boundary, which are determined by the minimum of the two run lengths.

Pro tip: Mention that this problem is similar to counting balanced substrings but with the additional grouping constraint, and that the O(n) solution is optimal because any valid substring must cross exactly one boundary between runs.

1. Clarify the problem and edge cases

Confirm that k >= 1 and that substrings must be contiguous. Discuss edge cases like empty string, all same characters, and strings with multiple runs.

2. Identify runs of identical characters

Scan the string and record the lengths of consecutive runs of 0s and 1s. For example, '0011100' becomes runs [2,3,2].

3. Count valid substrings at each boundary

For each adjacent pair of runs, the number of valid substrings that cross the boundary is the minimum of the two run lengths. Sum these counts.

4. Analyze time and space complexity

Explain that the algorithm runs in O(n) time and O(1) extra space if we process runs on the fly, or O(n) space if storing run lengths.

5. Test with examples

Walk through a few examples like '0011' (answer 2), '1100' (answer 2), '001100' (answer 4), and '0101' (answer 0) to verify correctness.

Key Points to Mention

Valid substrings must cross exactly one boundary between a run of 0s and a run of 1s.
The number of valid substrings at a boundary is min(length of left run, length of right run).
The total count is the sum over all adjacent run pairs.
Time complexity is O(n) and space complexity can be O(1) if runs are processed on the fly.
Edge cases: no valid substrings if all characters are the same or if runs alternate with length 1.
The solution can be implemented in a single pass by keeping track of the previous run length and the current run length.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.