Quick Overview

Given a string of digits, return every way to cut it into pieces whose integer values form a strictly increasing sequence, where no piece may start with zero. It tests exhaustive enumeration, leading-zero rules, comparing numbers that exceed 32 bits, and returning results in a defined order.

Split a Digit String into All Strictly Increasing Number Sequences

Company: Pinduoduo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given a string `s` of decimal digits, cut it into one or more contiguous pieces and read each piece as a decimal integer. Return every way of cutting `s` in which the resulting numbers form a strictly increasing sequence. No piece may start with the digit `0`. For example, for `s = "123045678"`, the splits `[1, 2, 30, 45, 678]` and `[1, 230, 45678]` are both valid, while any split that contains a piece such as `"045"` is not. ### Function Signature ```python def increasing_splits(s: str) -> list[list[int]]: ``` ### Rules - A split places cuts at any subset of the positions between adjacent characters, including no cut at all. The pieces, read left to right, concatenate back to `s`. With no cut, the split is the single number `int(s)`. - A piece is invalid if it starts with `'0'`; this includes `"045"`, `"00"` and `"0"`. A split that contains an invalid piece is not returned. - A split is valid when every number is strictly greater than the number before it. A one-piece split is valid whenever its piece is valid. - Return the valid splits as lists of integers, sorted in ascending lexicographic order: compare two splits number by number, as integers, and the split with the smaller number at the first position where they differ comes first. Two different splits of the same string always differ at some position, so this order is unique. ### Constraints - `1 <= len(s) <= 15` - `s` contains only the characters `'0'` to `'9'`, and `s[0] != '0'`. - A piece can have up to 15 digits, so a number can be as large as `10^15 - 1`. That exceeds the 32-bit signed range, so use 64-bit integers outside Python; every value stays below 2^53. - Because `s` does not start with `'0'`, the uncut split `[int(s)]` is always valid, so the result is never empty. ### Examples **Example 1** ```text Input: s = "1234" Output: [[1, 2, 3, 4], [1, 2, 34], [1, 234], [12, 34], [1234]] ``` The other three splits, `[1, 23, 4]`, `[12, 3, 4]` and `[123, 4]`, each contain a number that is not greater than the one before it. **Example 2** ```text Input: s = "1023" Output: [[10, 23], [1023]] ``` Every split with a cut right after the `1` has a piece that starts with `0` (`"023"`, `"0"` or `"02"`). Of the remaining splits, `[102, 3]` and `[10, 2, 3]` decrease. **Example 3** ```text Input: s = "321" Output: [[3, 21], [321]] ``` `[32, 1]` and `[3, 2, 1]` decrease.

Overview: Given a string of digits, return every way to cut it into pieces whose integer values form a strictly increasing sequence, where no piece may start with zero. It tests exhaustive enumeration, leading-zero rules, comparing numbers that exceed 32 bits, and returning results in a defined order.

Given a string `s` of decimal digits, cut it into one or more contiguous pieces and read each piece as a decimal integer. Return every way of cutting `s` in which the resulting numbers form a strictly increasing sequence. No piece may start with the digit `0`. For example, for `s = "123045678"`, the splits `[1, 2, 30, 45, 678]` and `[1, 230, 45678]` are both valid, while any split that contains a piece such as `"045"` is not. ### Rules - A split places cuts at any subset of the positions between adjacent characters, including no cut at all. The pieces, read left to right, concatenate back to `s`. With no cut, the split is the single number `int(s)`. - A piece is invalid if it starts with `'0'`; this includes `"045"`, `"00"` and `"0"`. A split that contains an invalid piece is not returned. - A split is valid when every number is strictly greater than the number before it. A one-piece split is valid whenever its piece is valid. - Return the valid splits as lists of integers, sorted in ascending lexicographic order: compare two splits number by number, as integers, and the split with the smaller number at the first position where they differ comes first. Two different splits of the same string always differ at some position, so this order is unique. Return a list of lists of integers (Python `list[list[int]]`, a JavaScript array of arrays of numbers, Java `java.util.List<java.util.List<Long>>`, C++ `std::vector<std::vector<long long>>`). ### Constraints - `1 <= len(s) <= 15` - `s` contains only the characters `'0'` to `'9'`, and `s[0] != '0'`. - A piece can have up to 15 digits, so a number can be as large as `10^15 - 1`. That exceeds the 32-bit signed range (`2^31 - 1`), so use 64-bit integers outside Python (Java `long`, C++ `long long`); every value stays below `2^53`. - Because `s` does not start with `'0'`, the uncut split `[int(s)]` is always valid, so the result is never empty. ### Example 1 ```text Input: s = "1234" Output: [[1, 2, 3, 4], [1, 2, 34], [1, 234], [12, 34], [1234]] ``` The other three splits, `[1, 23, 4]`, `[12, 3, 4]` and `[123, 4]`, each contain a number that is not greater than the one before it. ### Example 2 ```text Input: s = "1023" Output: [[10, 23], [1023]] ``` Every split with a cut right after the `1` has a piece that starts with `0` (`"023"`, `"0"` or `"02"`). Of the remaining splits, `[102, 3]` and `[10, 2, 3]` decrease.

Constraints

  • 1 <= len(s) <= 15
  • s contains only the characters '0' to '9', and s[0] != '0'
  • A piece can have up to 15 digits, so a number can be as large as 10^15 - 1, which exceeds 2^31 - 1: use 64-bit integers outside Python (Java long, C++ long long); every value stays below 2^53
  • Because s does not start with '0', the uncut split [int(s)] is always valid, so the result is never empty

Examples

Input: ('7',)

Expected Output: [[7]]

Explanation: Minimum valid input: a single digit has only the uncut split.

Input: ('1234',)

Expected Output: [[1, 2, 3, 4], [1, 2, 34], [1, 234], [12, 34], [1234]]

Explanation: Source example 1: [1, 23, 4], [12, 3, 4] and [123, 4] are rejected; the shorter (smaller) piece comes first at the first differing position.

Hints

  1. A string of length n has only n - 1 places where a cut can go, and n is at most 15, so the number of possible splits is small.
  2. Whether the next piece is allowed depends only on its first character and on the number just before it. A piece that is too small may become large enough if it takes more digits.
  3. Two splits that share their first few numbers start their next piece at the same index. Which of those two next pieces is the smaller integer?

Loading coding console...

Show the approach

Approach

Backtracking over cut positions. A recursive search tracks the index pos where the next piece starts and the previous number prev (initially -1, below every valid piece, because a valid piece is at least 1). When pos reaches len(s), the pieces chosen so far form a complete valid split and a copy is recorded. When s[pos] is '0', every piece starting at pos is invalid, so the branch is abandoned. Otherwise the piece is extended one digit at a time, its value built incrementally as value * 10 + digit, and the search recurses only when that value is strictly greater than prev. A piece that is not greater than prev does not end the loop, because a longer piece starting at the same index can still be greater (for 54321, after 54 the piece 3 fails but 321 succeeds).

Ordering invariant: two splits that agree on their first k numbers start their next piece at the same index. Neither of those pieces starts with 0, so the shorter one has fewer digits and is the smaller integer. Trying piece lengths in increasing order therefore records every split with the smaller number at the first differing position before the others, which is exactly the required ascending lexicographic order, with no separate sort.

Correctness: every recorded path consists of pieces that concatenate back to s, none of which starts with 0, each strictly greater than the one before; conversely every valid split is reached by exactly one path, so each appears once. Edge cases: a single digit returns only itself; the uncut split is always produced because s[0] != '0'; equal adjacent numbers such as [12, 12] for 1212 are rejected by the strict comparison; pieces are compared as integers, not text, so [8, 9, 10] is valid; values up to 10^15 - 1 require 64-bit integers in Java and C++ and stay exact in JavaScript numbers because they are below 2^53.

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