Number of Same-End Substrings - Practice Coding Problems

Number of Same-End Substrings - Problem

Array Hash Table String Counting Prefix Sum Medium

You are given a 0-indexed string s, and a 2D array of integers queries, where queries[i] = [li, ri] indicates a substring of s starting from the index li and ending at the index ri (both inclusive), i.e. s[li..ri].

Return an array ans where ans[i] is the number of same-end substrings of queries[i].

A 0-indexed string t of length n is called same-end if it has the same character at both of its ends, i.e., t[0] == t[n - 1].

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

Input & Output

Example 1 — Basic Case

$ Input: s = "abcba", queries = [[0,4],[1,3]]

› Output: [7,4]

💡 Note: For query [0,4] (whole string): 'a' appears 2 times → 3 substrings, 'b' appears 2 times → 3 substrings, 'c' appears 1 time → 1 substring. Total: 7. For query [1,3] ("bcb"): 'b' appears 2 times → 3 substrings, 'c' appears 1 time → 1 substring. Total: 4.

Example 2 — Single Character

$ Input: s = "aaaa", queries = [[0,3]]

› Output: [10]

💡 Note: All characters are 'a', appearing 4 times. Using formula: 4×5/2 = 10 same-end substrings.

Example 3 — No Repeats

$ Input: s = "abcd", queries = [[0,3],[1,2]]

› Output: [4,2]

💡 Note: For [0,3]: each character appears once, so 1×2/2 × 4 = 4. For [1,2]: 'b' and 'c' each appear once, so 1×2/2 × 2 = 2.

Constraints

1 ≤ s.length ≤ 10⁴
1 ≤ queries.length ≤ 10⁴
s consists of only lowercase English letters
0 ≤ li ≤ ri < s.length

Visualization

Tap to expand

Understanding the Visualization

Input

String s and query ranges

Process

Count character frequencies in each range

Output

Apply formula n*(n+1)/2 for each character

Key Takeaway

🎯 Key Insight: For n identical characters, there are exactly n×(n+1)/2 same-end substrings possible

Asked in

G Google 45 M Microsoft 38 a Amazon 32 f Facebook 28

The key insight is that for any character appearing n times in a range, it contributes exactly n×(n+1)/2 same-end substrings. The optimal approach uses prefix sum arrays to precompute character counts, enabling O(1) query answering. Time: O(N + Q), Space: O(N × 26)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(N + Q)	O(N × 26)	Precompute character counts at each position to answer queries in O(1)
Character Frequency Count	O(Q × N)	O(1)	Count each character in the query range and use combinatorial formula
Brute Force	O(Q × N³)	O(1)	For each query, check all possible substrings within the range

Prefix Sum Optimization — Algorithm Steps

Build 2D prefix array counting each character up to each position
For each query [l,r], use prefix sums to get character counts instantly
Apply the same combinatorial formula n*(n+1)/2 for each character

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Array

Pre-calculate character counts up to each position

Range Query

Get count in [l,r] using prefix[r+1] - prefix[l]

Apply Formula

Use n*(n+1)/2 for each character

Code -

solution.c — C

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

int* solution(char* s, int queries[][2], int queryCount, int* returnSize) {
    int n = strlen(s);
    // Build prefix sum array for each character
    int prefix[n + 1][26];
    
    // Initialize first row to 0
    for (int c = 0; c < 26; c++) {
        prefix[0][c] = 0;
    }
    
    for (int i = 0; i < n; i++) {
        // Copy previous counts
        for (int c = 0; c < 26; c++) {
            prefix[i + 1][c] = prefix[i][c];
        }
        // Increment count for current character
        prefix[i + 1][s[i] - 'a']++;
    }
    
    int* result = (int*)malloc(queryCount * sizeof(int));
    *returnSize = queryCount;
    
    for (int q = 0; q < queryCount; q++) {
        int l = queries[q][0], r = queries[q][1];
        int total = 0;
        
        // Get character count in range [l, r] using prefix sums
        for (int c = 0; c < 26; c++) {
            int count = prefix[r + 1][c] - prefix[l][c];
            if (count > 0) {
                total += count * (count + 1) / 2;
            }
        }
        result[q] = total;
    }
    
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char queriesStr[10000];
    fgets(queriesStr, sizeof(queriesStr), stdin);
    
    // Simple parsing for queries
    int queries[100][2];
    int queryCount = 0;
    char* ptr = queriesStr;
    while ((ptr = strchr(ptr, '[')) != NULL) {
        ptr++;
        if (sscanf(ptr, "%d,%d", &queries[queryCount][0], &queries[queryCount][1]) == 2) {
            queryCount++;
        }
    }
    
    int returnSize;
    int* result = solution(s, queries, queryCount, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(N + Q)

O(N) to build prefix array, then O(1) per query

✓ Linear Growth

Space Complexity

O(N × 26)

2D prefix array storing count of each of 26 characters at each position

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

892 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