valid partition of a string such that segments are in increasing order

general
,
1

A string of digits is given, for example, “12335457”. A valid partition is a partition of the string such that each segment is strictly greater than that previous segment.

For example, “12 | 33 | 54 | 57” is a valid partition and 57 > 54 > 33 > 12. Another valid partition can be “12 | 335 | 457” .

How many valid partitions possible for the given string? The maximum length of the string can be 5000.

If we use dynamic programming with parameter i and j, which means, the last segment was from i … to …j, then we can recurse on the remaining part.

int solve(int i,int j) {
	// memoization need to be added
	int last_length = j - i + 1;
	int ans = 0;
	for(int k = j + last_length ; k < n ; k++) {
		if( segment(j+1,k) > segment(i,j) ) {
			// this is possible in O(1) even if segment lengths are equal
			// we should do some pre preocessing on the given string
			// which can take O(n^2) time
			// if segment(j+1,k) length is more than L , then it is trivial
			ans += solve(j+1 , k);
		}
	}
}

But this approach will take O(n^3) time. How can we reduce it from O(n^3)?

2

Let dp[i][j] denotes the number of valid partition of string s[1:i] where the last partition ranges from s[j:i]

So dp[i][j]=sum(dp[j-1][k])

Where j-1-k < i-j

i.e. k>2*j-1-i

if(s[j:i]>s[j-1-(i-j)][j-1])

dp[i][j]+=dp[j-1][j-1-(i-j)]

Ohk ,so reasoning,

If last segment is of length x,then we can obviously choose previous segment with length less than x .

If previous segment is also of same length,then check if last is greater.

Now basically u have to find sum(dp[j-1][k]) fast

So basically when u have calculated dp[i][j] for a given i and all j,u can just calculate suffix[i][j] where suffix[i][j]=sum(suffix[i][j+1]+dp[i][j])

Basically suffix[i][j] will now store sum(dp[i][j] to dp[i][i])