count no. of strings

Question

This question was asked in a coding round of a company in our placements.

Given a string consisting of numbers from 1 to 9. We have to arrange the string such that it is divided into groups. We need to count no. of possible strings such that sum of a group<= sum of next consecutive group.

Example1
input : 1234
output: 6
Strings are :

• {1,2,3,4}
• {1,2,34}
• {12,3,4}
• {12,34}
• {1,234}
• {1234}

the first combination here, 1<2<3<4. second combination, 1<2<(3+4). and so on.

Example2
input : 516
output : 3
Strings are :

• {5,16}
• {51,6}
• {516}

Now time taken by brute force way to generate all strings is O(2^(n-1)). My question is how to solve it in better than brute force way?

Constraint : input string length 1<=n<=1000

Answer 1

This problem can efficiently be solved using Dynamic Programming. I solved it using a two dimensional array called dp. To find the number of valid splits where the endth character is last and the last string starts from startth character, we need to use the previously computed and cached value for the number of valid splits which ends at the start-1th character. That number is a sum of all the cached values in dp[prev_start][start - 1], where prev_start may be any value between [0, start), such that the sum of elements in s[prev_start:start-1] is not greater than the sum of the elements in s[start:end]. Here is a solution in Python3:

def get_count(s):
    N = len(s)
    # Initialize memoization matrix
    # First row all ones, all others zeros
    dp = list()
    dp.append([1] * N)
    for i in range(N - 1):
        dp.append([0] * N)

    # Convert characters to integers
    s = [ord(i) - ord('0') for i in s]

    for start in range(1, N):
        for end in range(start, N):
            for prev_start in range(0, start):
                if sum(s[prev_start:start]) <= sum(s[start:end+1]):
                    dp[start][end] += dp[prev_start][start - 1]

    return sum([dp[i][N - 1] for i in range(N)])

print(get_count('516'))

Note: the time complexity is O(n^4), but you can easily optimize it to O(n^3).