LeetCode Problem 3817

Difficulty: 🟡 Medium
Topics: Math, String

Solution

LeetCode 3817 - Good Indices in a Digit String

Problem Understanding

We are given a string s consisting only of decimal digits. The string length is n, and indices are zero-based.

For every index i, we need to determine whether i is a good index. An index is considered good if there exists a substring ending exactly at position i whose contents equal the decimal representation of the number i.

In other words, let str(i) denote the decimal representation of the index. We need to check whether the characters immediately ending at position i form exactly that string.

For example, if i = 12, then str(i) = "12". The index is good if the substring ending at position 12 and having length 2 equals "12".

The input consists of a single digit string. The output should be an array containing all good indices in increasing order.

The constraints are important:

• 1 <= s.length <= 100000
• s contains only digits

A length of 100000 immediately rules out expensive substring checking for every possible start and end position. Any solution significantly worse than linear or near-linear time is likely too slow.

Some important observations and edge cases:

• Index 0 must be checked against the string "0".
• Multi-digit indices such as 10, 123, and 99999 must match their entire decimal representation.
• If the decimal representation is longer than the available prefix ending at i, then a match is impossible.
• Leading zeros matter because we are comparing strings exactly. For example, index 12 corresponds to "12", not "012".

Approaches

Brute Force

A straightforward approach is to iterate through every index i.

For each index:

1. Convert i to its decimal representation.
2. Let its length be k.
3. Check whether there are at least k characters ending at position i.
4. Extract the substring s[i-k+1:i+1].
5. Compare it with str(i).

This approach is correct because it directly implements the definition of a good index.

However, converting every index and creating substrings repeatedly is expensive. The length of an index representation can be up to O(log n), and substring creation may also cost proportional time. Across all indices, this results in O(n log n) work.

While this may actually pass for n = 100000, we can do better.

Key Insight

Notice that the only strings we ever need to match are the decimal representations of indices themselves.

Instead of asking:

For each index, does its representation appear here?

we can reverse the perspective:

For each index i, find where the string representation of i would start if it ended at position i.

Suppose:

• t = str(i)
• len(t) = k

Then the required substring must begin at:

start = i - k + 1

The index is good if:

start >= 0
and
s[start : start + k] == t

Since the maximum index is at most 99999, every representation has at most 5 digits because n <= 100000.

Therefore each comparison costs at most 5 character checks.

This means the total work is:

O(5 * n) = O(n)

which is effectively linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(log n)	Builds and compares variable-length substrings
Optimal	O(n)	O(1) excluding output	Each index requires checking at most 5 digits

Algorithm Walkthrough

1. Let n be the length of s.
2. Create an empty answer array.
3. Iterate through every index i from 0 to n - 1.
4. Convert the index into its decimal representation:

t = str(i)

5. Compute the length of the representation:

k = len(t)

6. Determine where this representation would need to start if it ended at index i:

start = i - k + 1

7. If start < 0, there are not enough characters available before index i, so this index cannot be good.
8. Otherwise compare the substring:

s[start : start + k]

with

t

9. If they are equal, append i to the answer array.
10. After processing all indices, return the answer.

Why it works

For an index i, any valid substring ending at i and equal to the decimal representation of i must have exactly len(str(i)) characters. Therefore its starting position is uniquely determined as i - len(str(i)) + 1.

The algorithm checks exactly this required substring. If it matches str(i), the definition of a good index is satisfied. If it does not match, no other substring ending at i can represent i because the required length is fixed. Therefore every good index is found, and no invalid index is included.

Python Solution

from typing import List

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

        for i in range(n):
            index_str = str(i)
            length = len(index_str)

            start = i - length + 1

            if start >= 0 and s[start:start + length] == index_str:
                answer.append(i)

        return answer

The implementation follows the algorithm directly.

For each index, we first compute its decimal representation. The representation length determines exactly where the matching substring must begin. If that start position would fall before the beginning of the string, the index cannot be good and is skipped.

Otherwise, we compare the corresponding substring against the decimal representation. When they match, the current index is appended to the answer list.

Because the largest possible index has at most five digits, each comparison is extremely small, making the overall solution linear.

Go Solution

func goodIndices(s string) []int {
	n := len(s)
	ans := make([]int, 0)

	for i := 0; i < n; i++ {
		indexStr := strconv.Itoa(i)
		length := len(indexStr)

		start := i - length + 1

		if start >= 0 && s[start:start+length] == indexStr {
			ans = append(ans, i)
		}
	}

	return ans
}

The Go solution is nearly identical to the Python version.

The main difference is that strconv.Itoa is used to convert an integer to its decimal string representation. String slicing in Go works similarly for ASCII digits, so comparing s[start:start+length] with indexStr is straightforward.

The function always returns a slice. If no good indices exist, an empty slice is returned.

Worked Examples

Example 1

Input:

s = "0234567890112"

i	str(i)	start	Required Substring	Match?
0	"0"	0	"0"	Yes
1	"1"	1	"2"	No
2	"2"	2	"3"	No
3	"3"	3	"4"	No
4	"4"	4	"5"	No
5	"5"	5	"6"	No
6	"6"	6	"7"	No
7	"7"	7	"8"	No
8	"8"	8	"9"	No
9	"9"	9	"0"	No
10	"10"	9	"01"	No
11	"11"	10	"11"	Yes
12	"12"	11	"12"	Yes

Result:

[0, 11, 12]

Example 2

Input:

s = "01234"

i	str(i)	start	Required Substring	Match?
0	"0"	0	"0"	Yes
1	"1"	1	"1"	Yes
2	"2"	2	"2"	Yes
3	"3"	3	"3"	Yes
4	"4"	4	"4"	Yes

Result:

[0, 1, 2, 3, 4]

Example 3

Input:

s = "12345"

i	str(i)	start	Required Substring	Match?
0	"0"	0	"1"	No
1	"1"	1	"2"	No
2	"2"	2	"3"	No
3	"3"	3	"4"	No
4	"4"	4	"5"	No

Result:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index performs a comparison involving at most 5 characters
Space	O(1)	Only a few variables are used, excluding the output array

The key observation is that n <= 100000, so every index has at most five decimal digits. Therefore the substring comparison for each position is bounded by a constant. Processing all indices requires linear time overall.

Test Cases

from typing import List

def run_test(s: str, expected: List[int]):
    result = Solution().goodIndices(s)
    assert result == expected, f"{s}: expected {expected}, got {result}"

# Provided examples
run_test("0234567890112", [0, 11, 12])  # example 1
run_test("01234", [0, 1, 2, 3, 4])      # example 2
run_test("12345", [])                    # example 3

# Minimum length
run_test("0", [0])                       # single matching character
run_test("9", [])                        # single non-matching character

# Two-character strings
run_test("01", [0, 1])                   # both indices match
run_test("00", [0])                      # only index 0 matches

# Multi-digit match
run_test("000000000011", [0, 11])        # index 11 appears at end

# No matches beyond index 0
run_test("099999999999", [0])            # only index 0 valid

# Consecutive multi-digit matches
run_test("0123456789101112",
         [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

# Long repeated zeros
run_test("0" * 100, [0])                 # stress many failed checks

# Match near boundary where representation length changes
run_test("012345678910", list(range(11)))  # includes index 10

Test Summary

Test	Why
"0234567890112"	Official example with multi-digit matches
"01234"	Every index is good
"12345"	No index is good
"0"	Minimum valid input
"9"	Minimum input with no match
"01"	Small string with multiple matches
"00"	Verifies selective matching
"000000000011"	Multi-digit index match
"099999999999"	Mostly failures
"0123456789101112"	Consecutive multi-digit matches
"0" * 100	Stress case with many unsuccessful checks
"012345678910"	Boundary crossing from one digit to two digits

Edge Cases

Index Representation Longer Than Available Prefix

Consider an index such as 10. Its representation has length 2. If the string position being checked does not have two available characters ending at that location, a match is impossible.

This can easily cause out-of-bounds errors in a careless implementation. The algorithm handles this by computing start = i - length + 1 and requiring start >= 0 before any substring comparison is attempted.

Leading Zeros in the String

A substring such as "012" does not represent index 12. The required representation for index 12 is exactly "12".

Because the algorithm performs exact string comparison with str(i), leading zeros never produce false positives.

Transition Between Digit Lengths

Indices move from one digit to two digits at 10, from two digits to three digits at 100, and so on.

These boundaries are a common source of off-by-one mistakes. By computing the start position directly from len(str(i)), the implementation automatically handles all digit-length transitions correctly without any special cases.

Very Large Input Length

The maximum length is 100000. A quadratic solution would be far too slow.

The implementation only performs one bounded-size comparison per index. Since each index representation contains at most five digits, the running time grows linearly with the input size and remains efficient even at the maximum constraint.