Count Substrings Starting and Ending with Given Character

Medium
1024.

Count Substrings Starting and Ending with Given Character

Count Substrings Starting and Ending with Given Character is a medium coding problem on strings, math and counting, asked in Amazon, Google and Oracle interviews.

Return the number of substrings of s that both start and end with the character c. A single occurrence of c counts as a substring of length one.

Example 1

Input
s = "codekairo", c = "o"
Output
3
Explanation
The two `o`s give `o`, `o` and `odekairo`.

Example 2

Input
s = "abada", c = "a"
Output
6
Explanation
Three `a`s give 3 + 2 + 1 = 6 substrings.

Example 3

Input
s = "zzz", c = "z"
Output
6

Constraints

  • 1 <= s.length <= 10^4
  • s and c consist only of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} c
 * @return {number}
 */
var countSubstrings = function(s, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Substrings Starting and Ending with Given Character Solution

Count Substrings Starting and Ending with Given Character solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Substrings Starting and Ending with Given Character is a medium coding problem on strings, math and counting, asked in Amazon, Google and Oracle interviews.

  • Difficulty: Medium
  • Topics: Strings, Math, Counting
  • Asked at: Amazon, Google, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the number of substrings of s that both start and end with the character c. A single occurrence of c counts as a substring of length one.

Example 1

Input: s = "codekairo", c = "o"
Output: 3
Explanation: The two `o`s give `o`, `o` and `odekairo`.

Example 2

Input: s = "abada", c = "a"
Output: 6
Explanation: Three `a`s give 3 + 2 + 1 = 6 substrings.

Example 3

Input: s = "zzz", c = "z"
Output: 6

Constraints

  • 1 <= s.length <= 10^4
  • s and c consist only of lowercase English letters.

Hints for Count Substrings Starting and Ending with Given Character

  1. Hint 1

    A qualifying substring is determined entirely by which occurrence of c it starts at and which it ends at.

  2. Hint 2

    If c occurs m times, how many ordered pairs (start, end) with start ≤ end are there?

  3. Hint 3

    The answer is m * (m + 1) / 2 — no substring is ever built.

How to solve Count Substrings Starting and Ending with Given Character

Count the occurrences of c. Every qualifying substring corresponds to a pair of occurrences — one for the start, one for the end, with the start no later than the end — so the answer is m choose 2 plus the m single-character substrings, which is m(m+1)/2.

Approach

  1. Count how many times c appears in s.
  2. Return m * (m + 1) / 2.

Why it works

Everything between the two chosen occurrences is irrelevant — the substring is fixed once its endpoints are. That turns an apparent O(n²) enumeration into a single count, which is what the 10⁴ bound is really testing. The + m term is easy to lose: an occurrence paired with itself is a valid length-one substring.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Length-one substrings count — do not use m * (m - 1) / 2.
  • Enumerating substrings directly is O(n²) and far too slow at the upper bound.
  • m * (m + 1) is always even, so the integer division is exact.

Reference solution

Python

def countSubstrings(s: str, c: str) -> int:
    m = s.count(c)
    return m * (m + 1) // 2

Java

public static int countSubstrings(String s, String c) {
    long m = 0;
    char target = c.charAt(0);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == target) m++;
    }
    return (int) (m * (m + 1) / 2);
}

C++

int countSubstrings(string s, string c) {
    long long m = 0;
    char target = c[0];
    for (char ch : s) {
        if (ch == target) m++;
    }
    return (int) (m * (m + 1) / 2);
}

JavaScript

var countSubstrings = function(s, c) {
    var m = 0;
    for (var i = 0; i < s.length; i++) if (s.charAt(i) === c) m++;
    return m * (m + 1) / 2;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings