Restore The Array

Restore The Array

What is this problem about?

The Restore The Array interview question gives you a string of digits and an integer k. You must count the number of ways to split the string into a sequence of positive integers (no leading zeros, each value between 1 and k inclusive) such that concatenating them all gives back the original string. The result should be returned modulo 10^9 + 7.

Why is this asked in interviews?

Google and Postman ask this HARD dynamic programming problem because it tests the ability to apply DP to string segmentation with numerical constraints. It combines digit-string parsing with DP state transitions and requires careful handling of leading zeros and value-range bounds. String DP with numeric constraints appears in parsing, compiler design, and data validation systems.

Algorithmic pattern used

The pattern is dynamic programming on string indices. Define dp[i] = number of ways to split s[i:] into valid integers. Iterate from the end to the start. For each index i, try all valid segment lengths starting from s[i]: take 1 to len(str(k)) digits, parse the value, and if it is between 1 and k (and has no leading zero), add dp[i + segment_length] to dp[i]. Base case: dp[n] = 1 (empty suffix has one way to be split: the empty split).

Example explanation

s = "1317", k = 2000.

dp[4] = 1 (base).

• dp[3]: try "7" (value 7, valid) → dp[4]=1. dp[3]=1.
• dp[2]: try "1" (value 1) → dp[3]=1. Try "17" (value 17) → dp[4]=1. dp[2]=2.
• dp[1]: try "3" → dp[2]=2. Try "31" → dp[3]=1. Try "317" → dp[4]=1. dp[1]=4.
• dp[0]: try "1" → dp[1]=4. Try "13" → dp[2]=2. Try "131" → dp[3]=1. Try "1317" (value 1317 ≤ 2000) → dp[4]=1. dp[0]=8.

Result: 8 ways.

Common mistakes candidates make

• Not handling leading zeros — if s[i] == '0', no valid segment starts at i.
• Not limiting the segment length to the number of digits in k, which bounds the search.
• Forgetting the modulo operation on each addition.
• Parsing segments as strings and comparing lexicographically instead of numerically.

Interview preparation tip

For the Restore The Array coding problem, the string and dynamic programming interview pattern is the approach. Define your DP clearly: dp[i] = ways to split s[i:]. Iterate backwards. The key optimization: limit segment length to len(str(k)) to avoid scanning unnecessarily long substrings. Google interviewers value concise DP definitions and clean transition logic — write the recurrence on the board before coding.