Count Sorted Digit Groupings

Intuition

We split the digit string into contiguous groups such that group sums are non-decreasing. At each index, choose the next cut position, compute current group sum, and recurse only if current sum is at least the previous group sum. This creates overlapping subproblems based on (index, previousSum), so memoization is effective.

Algorithm

1Define dfs(i, prevSum) = number of valid ways to partition substring starting at i.
2Base case: if i == n, return 1 (a complete valid partition).
3Iterate j from i to n-1, accumulating currSum of s[i..j].
4If currSum >= prevSum, add dfs(j+1, currSum) to answer.
5Memoize result for key (i, prevSum) and return it.
6Initial call is dfs(0, -1) so the first group is always allowed.

Example Walkthrough

Input: s = "1119"

1.Possible groupings include [1|1|1|9] with sums 1,1,1,9 and [11|19] with sums 2,10.
2.Grouping [1|11|9] has sums 1,2,9 and is valid.
3.Any grouping with decreasing next sum is discarded during DFS checks.

Output: 7

Common Pitfalls

•Memo key must include both index and previous sum; index alone is insufficient.
•Without memoization, recursion becomes exponential due to repeated states.
•Be careful with sum accumulation inside loop; reset correctly per DFS call.

Count Sorted Digit Groupings.java

Java


import java.util.*;

// Approach: DFS + memoization over partition positions.
// Build groups from left to right and allow a cut only when current group digit-sum >= previous group digit-sum.
// Memo state is (index, previousSum) to avoid recomputation of overlapping subproblems.
// Time: O(n * S * n) in worst case, Space: O(n * S), where S is possible digit-sum range.

class Solution {

    HashMap<String, Integer> mp;

    private int dfs(String s, int i, int n, int prv) {
        if (i == n) {
            return 1;
        }
        int dig = 0, cnt = 0;
        String ky = String.valueOf(i) + "&" + String.valueOf(prv);
        if (mp.containsKey(ky)) {
            return mp.get(ky);
        }
        for (int j = i; j < n; j++) {
            int x = s.charAt(j) - '0';
            dig += x;
            if (dig >= prv) {
                cnt += dfs(s, j + 1, n, dig);
            }
        }
        mp.put(ky, cnt);
        return cnt;
    }

    public int validGroups(String s) {
        mp = new HashMap<>();
        int n = s.length();
        return dfs(s, 0, n, -1);
    }
}

Was this solution helpful?