Split Array into Fibonacci Sequence

Problem Statement

In the given task, the objective is to dissect a string containing digits into a sequence that mirrors the properties of a Fibonacci sequence—where each number is the sum of the two preceding ones. These extracted sequences must adhere strictly to certain conditions:

• Each number in the sequence must be representable as a 32-bit signed integer.
• The sequence should contain a minimum of three numbers.
• Each sequence part should conform to the Fibonacci rule, specifically, the third number should be the sum of the first two and so forth.
• A sequence part cannot begin with extra zeros unless the part itself is zero. The challenge expects a solution to either return such a Fibonacci-like sequence extracted from the provided string, or an empty sequence when such extraction is not feasible.

Examples

Example 1

Input:

num = "1101111"

Output:

[11,0,11,11]

Explanation:

The output [110, 1, 111] would also be accepted.

Example 2

Input:

num = "112358130"

Output:

[]

Explanation:

The task is impossible.

Example 3

Input:

num = "0123"

Output:

[]

Explanation:

Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Constraints

• 1 <= num.length <= 200
• num contains only digits.

Approach and Intuition

This problem can be approached by carefully partitioning the input string into valid numeric blocks and repeatedly checking the Fibonacci condition. The constraints and assumptions outlined suggest the following approach:

1. Analyze the string in chunks that might form potential Fibonacci sequence starters.

2. Starting with the smallest possible valid number, generate possible sequences and validate them:

   • For each chosen pair of starting numbers in the sequence, simulate the generation of the next numbers based exclusively on the Fibonacci-like summing property.
   • For every new number, check if it matches the start of the remaining unprocessed portion of the string.
   • Continue this process until either the entire string is consumed by the sequence or it becomes impossible to continue the sequence based on the remainder of the string.

3. Consider practical boundaries for searches based on string length and possible integer sizes (32-bit restriction).

4. Cycle through potential starting pairs with careful attention to the rules regarding leading zeros.

Given the indicated constraints (string length up to 200 characters):

• The choice of starting block sizes must be managed efficiently because the possible combinations grow exponentially with longer strings.
• Use a loop through the string to pick a starting number, then a nested loop for the second number, and check if continuing the pattern could exhaust the string correctly. If a valid sequence satisfying all conditions is found, it should be returned immediately. If no sequences are found after exhausting all pairs, return an empty list.

The edge cases, such as strings that contain a series of zeros, or strings that are too short to form a sequence, should be handled from the outset to prevent unnecessary computation.

Solutions

class Solution {
    public List<Integer> generateFibonacciSequence(String input) {
        int length = input.length();
        for (int i = 0; i < Math.min(10, length); ++i) {
            if (input.charAt(0) == '0' && i > 0) break;
            long firstNum = Long.parseLong(input.substring(0, i+1));
            if (firstNum >= Integer.MAX_VALUE) break;

            outerLoop: for (int j = i+1; j < Math.min(i+10, length); ++j) {
                if (input.charAt(i+1) == '0' && j > i+1) break;
                long secondNum = Long.parseLong(input.substring(i+1, j+1));
                if (secondNum >= Integer.MAX_VALUE) break;

                List<Integer> fibSequence = new ArrayList<>();
                fibSequence.add((int) firstNum);
                fibSequence.add((int) secondNum);

                int nextIndex = j + 1;
                while (nextIndex < length) {
                    long nextNum = fibSequence.get(fibSequence.size() - 2) + fibSequence.get(fibSequence.size() - 1);
                    String nextNumStr = String.valueOf(nextNum);

                    if (nextNum <= Integer.MAX_VALUE && input.substring(nextIndex).startsWith(nextNumStr)) {
                        nextIndex += nextNumStr.length();
                        fibSequence.add((int) nextNum);
                    }
                    else continue outerLoop;
                }
                if (fibSequence.size() >= 3) return fibSequence;
            }
        }

        return new ArrayList<Integer>();
    }
}