Binary String Split
Filed under Google
Free read 2 of 3Generate powers of 5 and convert them to binary strings.
The question
Split a binary string into the minimum number of substrings such that each substring is a binary representation of a power of 5 (e.g., 5^0=1, 5^1=5(101), 5^2=25(11001)).
Constraints
- String length up to 1000
- Return -1 if no valid split exists
Examples
- Input
- s = '101101'
- Output
- 2
- Why
- '101' is 5, '101' is 5. Total 2 parts.
Approach
Generate powers of 5 and convert them to binary strings.
dp[i] = min splits for prefix of length i.
dp[i] = min(dp[j] + 1) for all j < i where s[j:i] is a power of 5.
Tips
- What they are testing: Tests dynamic programming or greedy approach with backtracking.
- Common mistake: Assuming a greedy approach works without verifying if the remainder can be split.
Related Google questions
Collected from public candidate posts and coding forums. Updated Nov 2026.