Loading…

mediumDynamic ProgrammingSometimes asked

Sam and Substrings

Q: How do you solve Sam and Substrings using the Brute Force — Enumerate Every Substring approach?

When to use it: State it to define the quantity precisely, then optimise once the O(n²) cost is clear. Enumerate every substring and add its value. **The double loop.** Fix a start `l`. Sweep `r` from `l` to the end, maintaining the numeric value of `s[l..r]` incrementally: each step does `value = value·10 + digit[r]`, which is the value of the one-longer substring. Add `value` to the total at every step. **Why incremental building matters.** If you re-parsed each substring from scratch you'd pay O(length) per substring → O(n³). Building `value` as you extend `r` keeps it O(1) per substring, so the brute force is O(n²), not O(n³). **Why it's still too slow.** At `n = 2·10⁵`, `n²` is 4·10¹⁰ operations — far beyond a time limit. The fix is to notice we're recomputing closely related sums and to collapse the inner loop into a single recurrence per position. **Modulus.** Reduce `value` and `total` each step so they never overflow. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Sam and Substrings using the Positional DP — Sum of Substrings Ending Here (Optimal) approach?

When to use it: The answer they want. Phrase it as 'group substrings by their right end and use a place-value recurrence'. Group substrings by their right endpoint and find how consecutive groups relate. **The state.** Let `dp[i]` be the sum of the numeric values of all substrings that *end* at index `i`. There are exactly `i+1` such substrings: those starting at `0, 1, …, i`. **The recurrence.** Compare substrings ending at `i` with those ending at `i−1`. Take any substring `s[l..i−1]` (there are `i` of them, summing to `dp[i−1]`). Appending digit `d = digit[i]` turns it into `s[l..i]`, whose value is `value(s[l..i−1])·10 + d`. Summing over all such `l`: the `·10` part contributes `dp[i−1]·10`, and the `+d` part contributes `d` once for each of those `i` substrings → `i·d`. Finally, the new single-character substring `s[i..i]` adds one more `d`. Total: `dp[i] = dp[i−1]·10 + i·d + d = dp[i−1]·10 + (i+1)·d`. **Why the (i+1) factor.** It's the count of substrings ending at `i`. Each one acquires the digit `d` as its new last digit, contributing `d` apiece. Forgetting this and adding only a single `d` is the classic bug. **The answer.** `dp[i]` is only the substrings ending at `i`. The total over *all* substrings is `Σ dp[i]`, so maintain a running `total += dp[i]`. **Modulus.** Both the `·10` shift and the accumulation grow fast; reduce `dp` and `total` modulo 1e9+7 each step. Multiplication and addition commute with the modulus, so the reduced result equals the true sum mod 1e9+7. **Space.** `dp[i]` depends only on `dp[i−1]`, so one scalar suffices — O(1) space. Time complexity: O(n). Space complexity: O(1).

Dynamic Programming · 37 of 44 · 10 min

Given an integer represented as a string of digits, consider every substring of it as a number. Compute the sum of all these substring values, and return it modulo 1e9 + 7.

For example, for the string "16" the substrings are "1", "6", and "16", i.e. the numbers 1, 6, and 16, summing to 23.

In plain English

Every contiguous slice of the digit string is a number; we want them all added together. Listing all O(n²) substrings and parsing each is too slow for large inputs. The insight is to group substrings by where they end: when you move the right end one digit to the right, all the previously-ending substrings simply gain a digit on the right (their value times ten), and a brand-new single-digit substring appears. That gives a one-line update per position.

Examples

Example 1

Input: s = "16"
Output: 23
Note: Substrings: 1, 6, 16. Sum = 1 + 6 + 16 = 23.

Example 2

Input: s = "123"
Output: 164
Note: Substrings: 1, 2, 3, 12, 23, 123. Sum = 1+2+3+12+23+123 = 164.

Example 3

Input: s = "6759"
Output: 8421
Note: dp values 6, 74, 755, 7586; running total 6+74+755+7586 = 8421.

Constraints

1 ≤ |s| ≤ 2·10⁵
s consists of decimal digits (it may contain leading zeros in substrings)
The answer can be enormous → return it modulo 1 000 000 007
Substrings are contiguous

Clarifying questions4First question: Are substrings contiguous, or do you mean subsequences?Explore questions

Q1.Are substrings contiguous, or do you mean subsequences?
Contiguous substrings. 'Sub' here means a slice s[l..r]; subsequences would be a different (and harder) counting problem.
Q2.How should leading zeros be treated?
A substring like "05" is just the number 5. Numerically, leading zeros vanish automatically when you build the value digit by digit, so no special handling is needed.
Q3.Why a modulus?
For |s| up to 2·10⁵, substring values reach hundreds of thousands of digits and the sum is astronomically large. The problem asks for it modulo 1e9+7, so reduce as you go.
Q4.Does the ×10 place-value shift stay correct under the modulus?
Yes — multiplication and addition are compatible with modular reduction, so reducing dp and total each step preserves the exact answer mod 1e9+7.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Given a numeric string, sum the integer values of all its substrings, modulo 1e9+7. The key is a positional DP: let dp[i] = the sum of all substrings that END at index i. A substring ending at i is some substring ending at i−1 shifted left one digit (×10) with digit[i] appended, plus the single-digit substring [i] itself. There are (i+1) substrings ending at i, so dp[i] = dp[i−1]·10 + (i+1)·digit[i]. The answer is the sum of dp[i] over all i. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the per-position recurrence (dp[i] = dp[i−1]·10 + (i+1)·digit) instead of enumerating O(n²) substrings, and handle the modulus and place-value correctly.

Where candidates slip

Forgetting the (i+1) multiplier (treating the new digit as contributing once instead of once per substring ending at i), or returning the last dp instead of the running total.

How to stand out

Derive the recurrence from how substrings ending at i relate to those ending at i−1 (the ×10 place-value shift), then note it's O(n)/O(1) and modulo-safe.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Every Substring	`O(n²)`	`O(1)`	State it to define the quantity precisely, then optimise once the O(n²) cost is clear.	Read
2	Positional DP — Sum of Substrings Ending Here (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'group substrings by their right end and use a place-value recurrence'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Substrings ending at i from those ending at i−1

How to read it:Appending a digit shifts every prior substring by ×10 and adds a new single-digit one.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Every Substring

TimeO(n²)SpaceO(1)

State it to define the quantity precisely, then optimise once the O(n²) cost is clear.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For every start index l, extend an end index r to the right, building the current number value = value·10 + digit[r] as you go.

2Hint 2Explore hint

Add each value to a running total, reducing modulo 1e9+7.

3Hint 3Explore hint

This visits all n(n+1)/2 substrings — fine for small n, too slow at 2·10⁵.

A · Core idea

Enumerate every substring and add its value.

The double loop. Fix a start l. Sweep r from l to the end, maintaining the numeric value of s[l..r] incrementally: each step does value = value·10 + digit[r], which is the value of the one-longer substring. Add value to the total at every step.

Why incremental building matters. If you re-parsed each substring from scratch you'd pay O(length) per substring → O(n³). Building value as you extend r keeps it O(1) per substring, so the brute force is O(n²), not O(n³).

Why it's still too slow. At n = 2·10⁵, n² is 4·10¹⁰ operations — far beyond a time limit. The fix is to notice we're recomputing closely related sums and to collapse the inner loop into a single recurrence per position.

Modulus. Reduce value and total each step so they never overflow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "123"

Array state

l=0

1, 12, 123

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result164

C · Code with teaching comments

Reference implementation previewpublic long substrings(String s) { final long MOD = 1_000_000_007L; int n = s.length(); long total = 0; for (int l = 0; l < n; l++) {Explore the full code

solution.javaJava

Brute Force — Enumerate Every Substring — reference

3 teaching notes

1
public long substrings(String s) {
2
    final long MOD = 1_000_000_007L;
3
    int n = s.length();
4
    long total = 0;
5
    for (int l = 0; l < n; l++) {
6
        // Reset the running substring value for each new start.
7
        long value = 0;
8
        for (int r = l; r < n; r++) {
9
            // Extend the substring by one digit — value of s[l..r].
10
            value = (value * 10 + (s.charAt(r) - '0')) % MOD;
11
            // Add every substring's value; O(n²) of them.
12
            total = (total + value) % MOD;
13
        }
14
    }
15
    return total;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Even the O(n²) version already hints at the optimisation: for a fixed end r, all substrings ending at r share the place-value structure. Summing them in closed form per position removes the inner loop entirely.

ComplexityO(n²) time, O(1) space — Two nested loops over start and end indices visit O(n²) substrings, with O(1) work each (the value is built incrementally) → O(n²) time.

E · Edge cases and pitfalls3Re-parsing each substring from scratch → O(n³).Explore edge cases

Pitfalls

Re-parsing each substring from scratch → O(n³).
Forgetting the modulus and overflowing.
Running it at n = 2·10⁵ — O(n²) times out.

03.2

Approach 2 of 2 · Optimal

Positional DP — Sum of Substrings Ending Here (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'group substrings by their right end and use a place-value recurrence'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp = sum of values of all substrings ending at the current index. How does that relate to the sum for the previous index?

2Hint 2Explore hint

Adding digit d at index i takes every substring ending at i−1 and appends d (×10 then +d). The number of such substrings is i (their values are in dp[i−1]); plus the new single-digit substring d.

3Hint 3Explore hint

So dp[i] = dp[i−1]·10 + (i+1)·d, because there are i+1 substrings ending at i and each gains a +d. Accumulate dp[i] into the total.

A · Core idea

Group substrings by their right endpoint and find how consecutive groups relate.

The state. Let dp[i] be the sum of the numeric values of all substrings that end at index i. There are exactly i+1 such substrings: those starting at 0, 1, …, i.

The recurrence. Compare substrings ending at i with those ending at i−1. Take any substring s[l..i−1] (there are i of them, summing to dp[i−1]). Appending digit d = digit[i] turns it into s[l..i], whose value is value(s[l..i−1])·10 + d. Summing over all such l: the ·10 part contributes dp[i−1]·10, and the +d part contributes d once for each of those i substrings → i·d. Finally, the new single-character substring s[i..i] adds one more d. Total: dp[i] = dp[i−1]·10 + i·d + d = dp[i−1]·10 + (i+1)·d.

Why the (i+1) factor. It's the count of substrings ending at i. Each one acquires the digit d as its new last digit, contributing d apiece. Forgetting this and adding only a single d is the classic bug.

The answer. dp[i] is only the substrings ending at i. The total over all substrings is Σ dp[i], so maintain a running total += dp[i].

Modulus. Both the ·10 shift and the accumulation grow fast; reduce dp and total modulo 1e9+7 each step. Multiplication and addition commute with the modulus, so the reduced result equals the true sum mod 1e9+7.

Space. dp[i] depends only on dp[i−1], so one scalar suffices — O(1) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "6759"

Array state

i=0

dp=6, total=6

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result8421

C · Code with teaching comments

solution.javaJava

Positional DP — Sum of Substrings Ending Here (Optimal) — optimal

4 teaching notes

1
public long substrings(String s) {
2
    final long MOD = 1_000_000_007L;
3
    long dp = 0, total = 0;
4
    for (int i = 0; i < s.length(); i++) {
5
        // Numeric value of the current digit.
6
        int d = s.charAt(i) - '0';
7
        // Shift prior substrings by ×10 and add d once per (i+1) substrings ending at
8
        // i.
9
        dp = (dp * 10 + (long) (i + 1) * d) % MOD;
10
        // Accumulate substrings ending at i into the global sum.
11
        total = (total + dp) % MOD;
12
    }
13
    // Sum over all end positions = sum over all substrings.
14
    return total;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole trick is choosing the state 'sum of substrings ending at i'. Once framed that way, extending by one digit is a uniform place-value operation (×10) plus a count-weighted digit term — the quadratic enumeration telescopes into a single linear recurrence.

ComplexityO(n) time, O(1) space — A single pass over n digits with O(1) work per digit → O(n) time. Only the rolling dp and total are kept → O(1) space.

E · Edge cases and pitfalls7s = "9" — i=0: dp = 1·9 = 9; total = 9. Single digit returns itself.Explore edge cases

Edge cases handled

s = "9"i=0: dp = 1·9 = 9; total = 9. Single digit returns itself.
s = "16"dp 1 then 16; total 1 then 17? No: dp0=1 total=1; dp1=1·10+2·6=22 total=23 → 23.
s = "00"All digits 0 → dp stays 0, total 0. Leading zeros handled naturally.
s = "10"dp0=1 total=1; dp1=1·10+2·0=10 total=11. Substrings 1,0,10 → 11.

Pitfalls

Adding only a single d instead of (i+1)·d — undercounts the new digit's contribution.
Returning dp (last position only) instead of the running total.
Using int for (i+1)·d at large i — multiply in long before reducing.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long substrings(String s) { final long MOD = 1_000_000_007L; long dp = 0, total = 0; for (int i = 0; i < s.length(); i++) { int d = s.charAt(i) - '0';Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the (i+1) factor

The new digit becomes the last digit of all i+1 substrings ending at i, contributing d to each. Adding a single d undercounts.

Explore the code comparison

Don't write this

dp = (dp * 10 + d) % MOD          # only one copy of d

Write this instead

dp = (dp * 10 + (i + 1) * d) % MOD  # one d per substring ending at i

Returning dp instead of the total

dp[i] is only the substrings ending at i. The answer is Σ dp[i]; returning the last dp drops every earlier position.

Explore the code comparison

Don't write this

return dp;          // only substrings ending at the last index

Write this instead

return total;       // sum of dp[i] over all i

Overflow on (i+1)·d

For large i, (i+1)·d and dp·10 can exceed 32-bit. Multiply in 64-bit before reducing.

Explore the code comparison

Don't write this

dp = (dp * 10 + (i + 1) * d) % MOD;  // int (i+1)*d may overflow before promotion

Write this instead

dp = (dp * 10 + (long) (i + 1) * d) % MOD;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Positional 'sum of substrings ending here' DP (place-value contribution)

Code pattern to memorize

MOD = 1e9+7
dp = 0          # sum of substrings ending at the previous index
total = 0
for i, ch in enumerate(s):
    d = int(ch)
    dp = (dp * 10 + (i + 1) * d) % MOD   # i+1 substrings end at i
    total = (total + dp) % MOD
return total

Rules to remember

1Define dp[i] = sum of the numeric values of all substrings ending at index i — that's the state that makes the recurrence collapse.
2Appending digit d at position i multiplies every substring ending at i−1 by 10 (place-value shift) and then adds d to each.
3Exactly (i+1) substrings end at index i (starting at 0,1,…,i), so the appended digit contributes (i+1)·d, not just d.
4The global answer is the running sum of dp[i], not the final dp value — each dp[i] is only the substrings ending at i.
5Apply the modulus to both the dp update and the total; the place-value ×10 makes values grow fast.

Use this pattern when

Sum/aggregate over all substrings or subarrays where each extends the previous by one element
Place-value or contribution-per-position reasoning turns O(n²) enumeration into O(n)
'Sum of all subarray X' problems (sums, ORs, numeric values) with an additive recurrence
Answer modulo a large prime over exponentially-valued substrings

Choose another pattern when

You need the substrings themselves, not an aggregate → enumeration
Substrings are non-contiguous (subsequences) → different counting
The aggregate isn't decomposable per-position (e.g. distinct counts) → other techniques
Values fit easily and n is tiny → brute force is fine, DP overkill

Interview takeaway

Reframe 'sum over all substrings' as 'sum of substrings ending at each position', and a clean recurrence appears: each new digit shifts the previous bucket by ×10 and adds itself once per substring ending here. Contribution-per-position is the lever that turns quadratic enumeration into a single linear pass.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternContribution-per-position DP: reframe an aggregate over all substrings as a sum of 'aggregate of substrings ending at i', yielding a place-value recurrence dp[i] = dp[i−1]·10 + (i+1)·digit. The same 'best/sum ending here' framing powers Kadane's algorithm and Sum of Subarray Minimums — recognise it to turn O(n²) enumeration into O(n).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sum of Subarray Minimums
Coming soon
Contribution-per-position again, but each element's weight is how many subarrays it minimizes.
Subarray Sum Equals K
Coming soon
Prefix-sum aggregation over subarrays — same 'group by endpoint' mindset.
Maximum Subarray
Coming soon
Kadane's 'best ending here' is the maximization sibling of this 'sum ending here' DP.
Sam and Substrings — modular variants
Same recurrence with different aggregates (e.g. count of substrings divisible by k).

Same pattern

←

Red John is Back

Continue · Next problem

Sherlock and Cost

mediumDynamic ProgrammingSometimes asked

Sam and Substrings

Dynamic Programming · 37 of 44 · 10 min

Given an integer represented as a string of digits, consider every substring of it as a number. Compute the sum of all these substring values, and return it modulo 1e9 + 7.

For example, for the string "16" the substrings are "1", "6", and "16", i.e. the numbers 1, 6, and 16, summing to 23.

In plain English

Examples

Example 1

Input: s = "16"
Output: 23
Note: Substrings: 1, 6, 16. Sum = 1 + 6 + 16 = 23.

Example 2

Input: s = "123"
Output: 164
Note: Substrings: 1, 2, 3, 12, 23, 123. Sum = 1+2+3+12+23+123 = 164.

Example 3

Input: s = "6759"
Output: 8421
Note: dp values 6, 74, 755, 7586; running total 6+74+755+7586 = 8421.

Constraints

1 ≤ |s| ≤ 2·10⁵
s consists of decimal digits (it may contain leading zeros in substrings)
The answer can be enormous → return it modulo 1 000 000 007
Substrings are contiguous

Clarifying questions4First question: Are substrings contiguous, or do you mean subsequences?Explore questions

Q1.Are substrings contiguous, or do you mean subsequences?
Contiguous substrings. 'Sub' here means a slice s[l..r]; subsequences would be a different (and harder) counting problem.
Q2.How should leading zeros be treated?
A substring like "05" is just the number 5. Numerically, leading zeros vanish automatically when you build the value digit by digit, so no special handling is needed.
Q3.Why a modulus?
For |s| up to 2·10⁵, substring values reach hundreds of thousands of digits and the sum is astronomically large. The problem asks for it modulo 1e9+7, so reduce as you go.
Q4.Does the ×10 place-value shift stay correct under the modulus?
Yes — multiplication and addition are compatible with modular reduction, so reducing dp and total each step preserves the exact answer mod 1e9+7.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you find the per-position recurrence (dp[i] = dp[i−1]·10 + (i+1)·digit) instead of enumerating O(n²) substrings, and handle the modulus and place-value correctly.

Where candidates slip

Forgetting the (i+1) multiplier (treating the new digit as contributing once instead of once per substring ending at i), or returning the last dp instead of the running total.

How to stand out

Derive the recurrence from how substrings ending at i relate to those ending at i−1 (the ×10 place-value shift), then note it's O(n)/O(1) and modulo-safe.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate Every Substring	`O(n²)`	`O(1)`	State it to define the quantity precisely, then optimise once the O(n²) cost is clear.	Read
2	Positional DP — Sum of Substrings Ending Here (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'group substrings by their right end and use a place-value recurrence'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Substrings ending at i from those ending at i−1

How to read it:Appending a digit shifts every prior substring by ×10 and adds a new single-digit one.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate Every Substring

TimeO(n²)SpaceO(1)

State it to define the quantity precisely, then optimise once the O(n²) cost is clear.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

For every start index l, extend an end index r to the right, building the current number value = value·10 + digit[r] as you go.

2Hint 2Explore hint

Add each value to a running total, reducing modulo 1e9+7.

3Hint 3Explore hint

This visits all n(n+1)/2 substrings — fine for small n, too slow at 2·10⁵.

A · Core idea

Enumerate every substring and add its value.

Modulus. Reduce value and total each step so they never overflow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "123"

Array state

l=0

1, 12, 123

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result164

C · Code with teaching comments

Reference implementation previewpublic long substrings(String s) { final long MOD = 1_000_000_007L; int n = s.length(); long total = 0; for (int l = 0; l < n; l++) {Explore the full code

solution.javaJava

Brute Force — Enumerate Every Substring — reference

3 teaching notes

1
public long substrings(String s) {
2
    final long MOD = 1_000_000_007L;
3
    int n = s.length();
4
    long total = 0;
5
    for (int l = 0; l < n; l++) {
6
        // Reset the running substring value for each new start.
7
        long value = 0;
8
        for (int r = l; r < n; r++) {
9
            // Extend the substring by one digit — value of s[l..r].
10
            value = (value * 10 + (s.charAt(r) - '0')) % MOD;
11
            // Add every substring's value; O(n²) of them.
12
            total = (total + value) % MOD;
13
        }
14
    }
15
    return total;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — Two nested loops over start and end indices visit O(n²) substrings, with O(1) work each (the value is built incrementally) → O(n²) time.

E · Edge cases and pitfalls3Re-parsing each substring from scratch → O(n³).Explore edge cases

Pitfalls

Re-parsing each substring from scratch → O(n³).
Forgetting the modulus and overflowing.
Running it at n = 2·10⁵ — O(n²) times out.

03.2

Approach 2 of 2 · Optimal

Positional DP — Sum of Substrings Ending Here (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'group substrings by their right end and use a place-value recurrence'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Let dp = sum of values of all substrings ending at the current index. How does that relate to the sum for the previous index?

2Hint 2Explore hint

3Hint 3Explore hint

So dp[i] = dp[i−1]·10 + (i+1)·d, because there are i+1 substrings ending at i and each gains a +d. Accumulate dp[i] into the total.

A · Core idea

Group substrings by their right endpoint and find how consecutive groups relate.

The state. Let dp[i] be the sum of the numeric values of all substrings that end at index i. There are exactly i+1 such substrings: those starting at 0, 1, …, i.

The answer. dp[i] is only the substrings ending at i. The total over all substrings is Σ dp[i], so maintain a running total += dp[i].

Space. dp[i] depends only on dp[i−1], so one scalar suffices — O(1) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "6759"

Array state

i=0

dp=6, total=6

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result8421

C · Code with teaching comments

solution.javaJava

Positional DP — Sum of Substrings Ending Here (Optimal) — optimal

4 teaching notes

1
public long substrings(String s) {
2
    final long MOD = 1_000_000_007L;
3
    long dp = 0, total = 0;
4
    for (int i = 0; i < s.length(); i++) {
5
        // Numeric value of the current digit.
6
        int d = s.charAt(i) - '0';
7
        // Shift prior substrings by ×10 and add d once per (i+1) substrings ending at
8
        // i.
9
        dp = (dp * 10 + (long) (i + 1) * d) % MOD;
10
        // Accumulate substrings ending at i into the global sum.
11
        total = (total + dp) % MOD;
12
    }
13
    // Sum over all end positions = sum over all substrings.
14
    return total;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — A single pass over n digits with O(1) work per digit → O(n) time. Only the rolling dp and total are kept → O(1) space.

E · Edge cases and pitfalls7s = "9" — i=0: dp = 1·9 = 9; total = 9. Single digit returns itself.Explore edge cases

Edge cases handled

s = "9"i=0: dp = 1·9 = 9; total = 9. Single digit returns itself.
s = "16"dp 1 then 16; total 1 then 17? No: dp0=1 total=1; dp1=1·10+2·6=22 total=23 → 23.
s = "00"All digits 0 → dp stays 0, total 0. Leading zeros handled naturally.
s = "10"dp0=1 total=1; dp1=1·10+2·0=10 total=11. Substrings 1,0,10 → 11.

Pitfalls

Adding only a single d instead of (i+1)·d — undercounts the new digit's contribution.
Returning dp (last position only) instead of the running total.
Using int for (i+1)·d at large i — multiply in long before reducing.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the (i+1) factor

The new digit becomes the last digit of all i+1 substrings ending at i, contributing d to each. Adding a single d undercounts.

Explore the code comparison

Don't write this

dp = (dp * 10 + d) % MOD          # only one copy of d

Write this instead

dp = (dp * 10 + (i + 1) * d) % MOD  # one d per substring ending at i

Returning dp instead of the total

dp[i] is only the substrings ending at i. The answer is Σ dp[i]; returning the last dp drops every earlier position.

Explore the code comparison

Don't write this

return dp;          // only substrings ending at the last index

Write this instead

return total;       // sum of dp[i] over all i

Overflow on (i+1)·d

For large i, (i+1)·d and dp·10 can exceed 32-bit. Multiply in 64-bit before reducing.

Explore the code comparison

Don't write this

dp = (dp * 10 + (i + 1) * d) % MOD;  // int (i+1)*d may overflow before promotion

Write this instead

dp = (dp * 10 + (long) (i + 1) * d) % MOD;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Positional 'sum of substrings ending here' DP (place-value contribution)

Code pattern to memorize

MOD = 1e9+7
dp = 0          # sum of substrings ending at the previous index
total = 0
for i, ch in enumerate(s):
    d = int(ch)
    dp = (dp * 10 + (i + 1) * d) % MOD   # i+1 substrings end at i
    total = (total + dp) % MOD
return total

Rules to remember

1Define dp[i] = sum of the numeric values of all substrings ending at index i — that's the state that makes the recurrence collapse.
2Appending digit d at position i multiplies every substring ending at i−1 by 10 (place-value shift) and then adds d to each.
3Exactly (i+1) substrings end at index i (starting at 0,1,…,i), so the appended digit contributes (i+1)·d, not just d.
4The global answer is the running sum of dp[i], not the final dp value — each dp[i] is only the substrings ending at i.
5Apply the modulus to both the dp update and the total; the place-value ×10 makes values grow fast.

Use this pattern when

Sum/aggregate over all substrings or subarrays where each extends the previous by one element
Place-value or contribution-per-position reasoning turns O(n²) enumeration into O(n)
'Sum of all subarray X' problems (sums, ORs, numeric values) with an additive recurrence
Answer modulo a large prime over exponentially-valued substrings

Choose another pattern when

You need the substrings themselves, not an aggregate → enumeration
Substrings are non-contiguous (subsequences) → different counting
The aggregate isn't decomposable per-position (e.g. distinct counts) → other techniques
Values fit easily and n is tiny → brute force is fine, DP overkill

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Sum of Subarray Minimums
Coming soon
Contribution-per-position again, but each element's weight is how many subarrays it minimizes.
Subarray Sum Equals K
Coming soon
Prefix-sum aggregation over subarrays — same 'group by endpoint' mindset.
Maximum Subarray
Coming soon
Kadane's 'best ending here' is the maximization sibling of this 'sum ending here' DP.
Sam and Substrings — modular variants
Same recurrence with different aggregates (e.g. count of substrings divisible by k).

Same pattern

←

Red John is Back

Continue · Next problem

Sherlock and Cost