3817. Good Indices in a Digit String 🔒

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s made up of digits.

We want to find certain positions (indices) in the string that satisfy a special condition. An index i is called good if we can find a substring of s that ends exactly at index i and whose value equals the decimal representation of i itself.

In other words, for an index i, take its decimal representation as a string (for example, if i = 12, the decimal representation is "12", which has length 2). Then look at the substring of s that ends at position i and has the same length as this decimal representation. If this substring is exactly equal to the decimal representation of i, then i is a good index.

Your task is to return an integer array containing all good indices in increasing order.

For example:

If i = 0, its decimal representation is "0" (length 1). We check whether the substring of s ending at index 0 (which is just s[0]) equals "0".
If i = 25, its decimal representation is "25" (length 2). We check whether s[24..25] equals "25".

Note that for a substring to end at index i and match the decimal representation of i, there must be enough characters before index i to form a substring of the required length.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Checking for each index whether a short ending substring matches its decimal representation is a direct iteration with substring comparison.

Open in Flowchart

Intuition

The key observation is that the length of string s is at most 10^5. This means the largest possible index i is around 10^5, and its decimal representation has at most 6 digits (since 100000 has length 6).

Because each index has only a short decimal representation, the check for whether an index is good is very cheap. For any index i, we simply need to:

Convert i into its decimal string t = str(i), and let k = len(t) be its length.
Look at the substring of s of length k that ends at index i, which is s[i + 1 - k : i + 1].
Compare this substring with t. If they are equal, then i is a good index.

Since we only need to compare a short string (at most 6 characters) for each index, we can afford to simply loop through every index from 0 to len(s) - 1 and perform this direct comparison. This is why a straightforward simulation works well here.

One nice detail is that Python slicing handles out-of-range cases gracefully. If there are not enough characters before index i to form a substring of length k, the slice s[i + 1 - k : i + 1] will simply produce a shorter string, which automatically fails the equality check with t. So we do not need any extra boundary checks.

By collecting every index that passes the check while iterating in increasing order, the resulting array is naturally sorted in increasing order as required.

Solution Approach

Solution 1: Simulation

We observe that the maximum length of string s is 10^5, and the length of the decimal representation of index i is at most 6 (since the decimal representation of 10^5 is 100000, which has a length of 6). Therefore, we only need to check for each index i whether the substring corresponding to its decimal representation is equal to it.

The implementation follows these steps:

Prepare the answer container. We create an empty list ans to store all good indices.
Iterate over every index. We loop i from 0 to len(s) - 1, examining each position one by one.
Build the target string. For the current index i, we convert it into its decimal string t = str(i) and record its length k = len(t). This t is exactly what the substring ending at index i must match.
Extract and compare the substring. We take the slice s[i + 1 - k : i + 1], which is the substring of length k that ends at index i. If this slice equals t, then index i is good, and we append it to ans.
- Thanks to Python's slicing behavior, if i + 1 - k is negative (meaning there are not enough characters before index i), the slice simply returns a shorter string that cannot equal t. This removes the need for explicit boundary checks.
Return the result. Since we iterate in increasing order of i, the indices appended to ans are already sorted, so we directly return ans.

In terms of complexity, the time complexity is O(n × L), where n is the length of string s and L is the maximum length of the decimal representation of an index (at most 6). The space complexity is O(1) ignoring the output array, since we only use a constant amount of extra space for the temporary string t during each iteration.

Example Walkthrough

Let's trace through the solution approach using a small example.

Input: s = "0102510"

The string has length 7, so we examine indices i = 0 through i = 6. The characters are:

Index	0	1	2	3	4	5	6
`s[i]`	0	1	0	2	5	1	0

We initialize ans = [] and loop through each index.

Index i = 0:

t = str(0) = "0", so k = 1.
Slice: s[0 + 1 - 1 : 0 + 1] = s[0:1] = "0".
Compare "0" == "0" → match! Append 0. Now ans = [0].

Index i = 1:

t = str(1) = "1", so k = 1.
Slice: s[1:2] = "1".
Compare "1" == "1" → match! Append 1. Now ans = [0, 1].

Index i = 2:

t = str(2) = "2", so k = 1.
Slice: s[2:3] = "0".
Compare "0" == "2" → no match. Skip.

Index i = 3:

t = str(3) = "3", so k = 1.
Slice: s[3:4] = "2".
Compare "2" == "3" → no match. Skip.

Index i = 4:

t = str(4) = "4", so k = 1.
Slice: s[4:5] = "5".
Compare "5" == "4" → no match. Skip.

Index i = 5:

t = str(5) = "5", so k = 1.
Slice: s[5:6] = "1".
Compare "1" == "5" → no match. Skip.

Index i = 6:

t = str(6) = "6", so k = 1.
Slice: s[6:7] = "0".
Compare "0" == "6" → no match. Skip.

Result: ans = [0, 1].

To also showcase the multi-digit case and Python's graceful slicing, consider an index like i = 25 for some longer string:

t = str(25) = "25", so k = 2.
Slice: s[25 + 1 - 2 : 25 + 1] = s[24:26], the two characters ending at index 25.
If s[24:26] == "25", then 25 is good.

And if there were not enough characters before the index (for example, checking a 2-digit target near the start of the string), the slice s[i + 1 - k : i + 1] would produce a string shorter than k, which can never equal t. This is why no explicit boundary check is needed—the comparison fails automatically.

Since we iterate i in increasing order and append matches as we find them, ans comes out naturally sorted, ready to return.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def goodIndices(self, s: str) -> List[int]:
6        # Store all indices that satisfy the condition
7        result: List[int] = []
8
9        for i in range(len(s)):
10            # Convert the current index to its string representation
11            index_str = str(i)
12            # Length of the index string
13            length = len(index_str)
14
15            # Check if the substring of `length` characters ending at position i
16            # matches the string representation of the index itself
17            if s[i + 1 - length : i + 1] == index_str:
18                result.append(i)
19
20        return result
21```
22
23A few notes on the changes and the logic:
24
25**Naming improvements**
26- `ans` → `result`: more descriptive of what it holds.
27- `t` → `index_str`: clarifies it's the string form of the index.
28- `k` → `length`: clarifies it represents a length.
29
30**How the logic works**
31- For each position `i`, it forms the string of that index (e.g., `i = 12` → `"12"`).
32- It then looks back `length` characters in `s` (the slice `s[i + 1 - length : i + 1]`) and checks whether those characters exactly equal the index string.
33- Note: when `i + 1 - length` becomes negative for small `i`, Python slicing will not behave as a strict "ending at i" check, so a more robust version might explicitly guard against `i + 1 - length < 0`.
34
35**Alternative perspective (with bounds guard)**
36If you want to avoid any negative-index slicing surprises, you could add an explicit check:
37
38```python3
39from typing import List
40
41
42class Solution:
43    def goodIndices(self, s: str) -> List[int]:
44        result: List[int] = []
45
46        for i in range(len(s)):
47            index_str = str(i)
48            length = len(index_str)
49            start = i + 1 - length
50
51            # Only valid when the slice has a non-negative start
52            if start >= 0 and s[start : i + 1] == index_str:
53                result.append(i)
54
55        return result
56

1class Solution {
2    /**
3     * Finds all indices i such that the decimal string of i
4     * appears in s ending exactly at position i (inclusive).
5     *
6     * @param s the input string
7     * @return list of indices satisfying the condition
8     */
9    public List<Integer> goodIndices(String s) {
10        List<Integer> ans = new ArrayList<>();
11
12        for (int i = 0; i < s.length(); i++) {
13            // Convert the current index into its decimal string form
14            String target = String.valueOf(i);
15            int len = target.length();
16
17            // Compute the starting position of the substring that
18            // would end at index i (inclusive); skip if it goes out of bounds
19            int start = i + 1 - len;
20            if (start < 0) {
21                continue;
22            }
23
24            // Check whether the substring ending at i equals the index string
25            if (s.substring(start, i + 1).equals(target)) {
26                ans.add(i);
27            }
28        }
29
30        return ans;
31    }
32}
33

1class Solution {
2public:
3    vector<int> goodIndices(string s) {
4        vector<int> ans;                       // Stores all indices that satisfy the condition
5        int n = static_cast<int>(s.size());    // Length of the input string
6
7        for (int i = 0; i < n; ++i) {
8            string indexStr = to_string(i);     // String representation of the current index
9            int len = static_cast<int>(indexStr.size());  // Number of digits in the index
10
11            // The substring ending at index i must have enough characters
12            // to hold the full string representation of i.
13            if (i + 1 - len < 0) {
14                continue;                        // Not enough preceding characters, skip
15            }
16
17            // Extract the substring of length 'len' that ends at position i,
18            // then compare it with the index's string form.
19            if (s.substr(i + 1 - len, len) == indexStr) {
20                ans.push_back(i);                // Match found, record this index
21            }
22        }
23
24        return ans;                              // Return all qualifying indices
25    }
26};
27

1/**
2 * Finds all indices i in the string where the substring ending at position i
3 * (with length equal to the number of digits in i) matches the decimal
4 * representation of i itself.
5 *
6 * @param s - The input string to scan.
7 * @returns An array of indices that satisfy the matching condition.
8 */
9function goodIndices(s: string): number[] {
10    // Collection of indices that meet the criteria.
11    const result: number[] = [];
12
13    // Iterate over every position in the string.
14    for (let i = 0; i < s.length; i++) {
15        // Decimal string representation of the current index.
16        const indexStr = String(i);
17
18        // Number of characters needed to represent the index.
19        const len = indexStr.length;
20
21        // Extract the substring of length `len` that ends at position i,
22        // then compare it with the index's string representation.
23        if (s.slice(i + 1 - len, i + 1) === indexStr) {
24            result.push(i);
25        }
26    }
27
28    return result;
29}
30

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s.

The code iterates through each index i from 0 to n - 1, performing a single pass over the string. Within each iteration:

t = str(i) converts the index i to its string representation, which takes O(k) time where k is the number of digits in i.
The slice operation s[i + 1 - k : i + 1] extracts a substring of length k, taking O(k) time.
The comparison s[i + 1 - k : i + 1] == t also takes O(k) time.

Since k is the number of digits in i, it is bounded by O(log n). Although a strict analysis would yield O(n log n), the reference treats the digit count k as a small constant factor, so the overall time complexity is considered O(n).

Space Complexity: O(1), ignoring the space required for the answer.

The only extra space used is for the temporary string t (of length O(log n)) and the slice. These are negligible constant-level auxiliary structures compared to the input, so the space complexity is O(1), excluding the output list ans.

Common Pitfalls

Pitfall: Negative Start Index in Slicing Produces False Positives

The most common pitfall lies in relying on Python's slicing behavior with the expression s[i + 1 - length : i + 1] without explicitly guarding against a negative start index. While this often works, it can silently produce incorrect results in a specific edge case.

Why it happens

When i + 1 - length is negative, Python interprets the negative value as an offset from the end of the string, rather than treating it as "out of bounds." This means the slice no longer represents the substring that strictly "ends at index i with the required length." Instead, it may grab characters from the end of the string, leading to an accidental match.

Concrete example

Consider s = "100" and look at i = 0:

index_str = "0", length = 1
start = i + 1 - length = 0 + 1 - 1 = 0 → fine here.

Now consider a trickier case, s = "0" with i = 0, that works correctly. The real danger appears when the index's decimal length exceeds the available characters before it. Take s = "12" and examine i = 2... but i only ranges up to len(s) - 1 = 1, so this never triggers — which masks the bug for many test cases.

The genuine trap surfaces with strings where a negative start wraps around. For instance, s = "ab" (conceptually, with digits) and i = 1:

index_str = "1", length = 1, start = 1 → fine.

But consider i whose decimal length is larger than i + 1. The smallest such case is when length > i + 1. For i = 0, length = 1, so i + 1 - length = 0 (never negative). For larger i, length grows much slower than i, so in this particular problem the start rarely goes negative for valid indices — but it can when length momentarily exceeds the position. Example: a single-digit index never causes issues, yet the slicing approach's correctness depends entirely on this coincidence rather than on explicit logic.

The real-world failure

A clearer demonstration: imagine the index string is longer than the prefix available, e.g., a hypothetical where start = -1. With s = "12345" and a slice like s[-1:5], Python returns "5" (the last character), not an empty string. If that last character happens to equal the index representation, you get a false positive.

Solution: Add an Explicit Bounds Check

The robust fix is to guard against a negative start index explicitly, never depending on slicing edge behavior:

from typing import List


class Solution:
    def goodIndices(self, s: str) -> List[int]:
        result: List[int] = []

        for i in range(len(s)):
            index_str = str(i)
            length = len(index_str)
            start = i + 1 - length

            # Explicitly require a non-negative start so the slice
            # genuinely represents "a substring ending at i of the right length"
            if start >= 0 and s[start : i + 1] == index_str:
                result.append(i)

        return result

Why this works

The condition start >= 0 ensures the slice is taken from a valid, non-wrapping range.
Because of short-circuit evaluation, when start < 0 the slice comparison is never executed, eliminating any chance of a wrap-around false positive.
It makes the intent of the code self-documenting: a substring must have enough preceding characters to qualify, directly mirroring the problem's note that "there must be enough characters before index i."

General takeaway

Whenever you compute a slice start by subtraction (i + 1 - length), treat the possibility of a negative result as a first-class concern. Relying on language-specific slicing quirks may pass many test cases by luck, but an explicit bounds check guarantees correctness across all inputs and clearly communicates the constraint to anyone reading the code.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering