Number of Divisible Substrings - Practice Coding Problems

Number of Divisible Substrings - Problem

Each character of the English alphabet has been mapped to a digit as shown below:

a → 1, b → 2, c → 3, d → 4, e → 5, f → 6, g → 7, h → 8, i → 9, j → 1, k → 2, l → 3, m → 4, n → 5, o → 6, p → 7, q → 8, r → 9, s → 1, t → 2, u → 3, v → 4, w → 5, x → 6, y → 7, z → 8

A string is divisible if the sum of the mapped values of its characters is divisible by its length.

Given a string s, return the number of divisible substrings of s.

A substring is a contiguous non-empty sequence of characters within a string.

Input & Output

Example 1 — Simple String

$ Input: s = "asdf"

› Output: 10

💡 Note: Character values: a=1, s=1, d=4, f=6. All substrings: "a"(1÷1), "s"(1÷1), "d"(4÷1), "f"(6÷1), "as"(2÷2), "sd"(5÷2), "df"(10÷2), "asd"(6÷3), "sdf"(11÷3), "asdf"(12÷4). Count divisible ones: 10 total.

Example 2 — Single Character

$ Input: s = "a"

› Output: 1

💡 Note: Only one substring "a" with value 1 and length 1. Since 1 % 1 = 0, it's divisible.

Example 3 — Two Characters

$ Input: s = "ab"

› Output: 3

💡 Note: Substrings: "a"(1÷1=0), "b"(2÷1=0), "ab"(3÷2=1.5). Only "a" and "b" are divisible, plus single chars always divisible, total = 3.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with character-to-digit mapping

Process

Check all substrings for sum % length == 0

Output

Count of divisible substrings

Key Takeaway

🎯 Key Insight: Use modular arithmetic to efficiently check if substring sum is divisible by its length

Asked in

G Google 25 a Amazon 18 M Microsoft 12

The key insight is using character-to-digit mapping and checking if substring sum is divisible by length. Best approach uses prefix sum optimization to avoid recalculating sums. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n²)	O(1)	Optimize sum calculation using running totals
Brute Force	O(n³)	O(1)	Check every substring individually for divisibility
Hash Map with Remainder Tracking	O(n²)	O(1)	Use modular arithmetic to efficiently count divisible substrings

Prefix Sum Optimization — Algorithm Steps

For each start position
Extend substring one character at a time
Update running sum and check divisibility

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Fix starting character

Extend & Update

Add one character, update sum

Check Divisible

Test current sum % length == 0

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int charValue(char c) {
    return ((c - 'a') % 9) + 1;
}

int solution(char* s) {
    int count = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        int runningSum = 0;
        for (int j = i; j < n; j++) {
            runningSum += charValue(s[j]);
            int length = j - i + 1;
            
            if (runningSum % length == 0) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops to generate all substrings, but sum calculation is O(1)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for running sum

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

756 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler