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)?