Is Good Indices in a Digit String easy or hard?

The problem is typically classified as Medium because it requires recognizing the prefix-sum optimization. The brute force idea is straightforward, but identifying how to maintain running sums efficiently is the key step that leads to the optimal O(n) solution.

Good Indices in a Digit String Python/Java solution

In Python or Java, iterate through the string while converting each character to its numeric digit. Maintain a running prefix sum and compute the right-side sum using the total digit sum. This single-pass simulation keeps the implementation short and runs in O(n) time.

How to solve Good Indices in a Digit String in O(n)?

First compute the total sum of all digits in the string. Traverse the string while maintaining a running left sum. For index i, compute the right sum as totalSum - leftSum - digit[i]. If both sides are equal, record the index as good, then update the left sum.

What is the best approach for Good Indices in a Digit String?

The prefix sum simulation approach is the most efficient. Maintain a running sum of digits to the left of the current index and derive the right-side sum from the total digit sum. This allows you to check each index in constant time, producing an overall O(n) time complexity with O(1) extra space.

Is Good Indices in a Digit String asked at Google/Amazon/Meta?

Problems involving prefix sums and digit-string processing appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require balancing prefix and suffix values or scanning strings with running totals are common interview patterns.

What data structure is used in Good Indices in a Digit String?

The solution primarily relies on simple variables and arithmetic rather than complex data structures. A running prefix sum and the total digit sum are sufficient to compute the right-side sum dynamically while iterating through the string.

What is the time complexity of Good Indices in a Digit String?

The optimal solution runs in O(n) time where n is the length of the digit string. Each index is processed exactly once while maintaining a running prefix sum. The brute force approach that recomputes left and right sums for every index takes O(n^2) time.

Description Hints 3 Solution Video 14:18

3817. Good Indices in a Digit String

Medium85.3% acceptancePremium elsewhere, free here

You are given a string s consisting of digits.

An index i is called good if there exists a substring of s that ends at index i and is equal to the decimal representation of i.

Return an integer array of all good indices in increasing order.

Example 1:

Input: s = "0234567890112"

Output: [0,11,12]

Explanation:

At index 0, the decimal representation of the index is "0". The substring s[0] is "0", which matches, so index 0 is good.
At index 11, the decimal representation is "11". The substring s[10..11] is "11", which matches, so index 11 is good.
At index 12, the decimal representation is "12". The substring s[11..12] is "12", which matches, so index 12 is good.

No other index has a substring ending at it that equals its decimal representation. Therefore, the answer is [0, 11, 12].

Example 2:

Input: s = "01234"

Output: [0,1,2,3,4]

Explanation:

For every index i from 0 to 4, the decimal representation of i is a single digit, and the substring s[i] matches that digit.

Therefore, a valid substring ending at each index exists, making all indices good.

Example 3:

Input: s = "12345"

Output: []

Explanation:

No index has a substring ending at it that matches its decimal representation.

Therefore, there are no good indices and the result is an empty array.

Constraints:

1 <= s.length <= 10⁵
s only consists of digits from '0' to '9'.

Topics

Math String

Hints open one at a time

Hint 1

For an index i, any valid substring must end exactly at position i.

Hint 2

The substring you are looking for is determined by the decimal digits of i.

Hint 3

For each index i, compare the string form of i with the substring that ends at i and has the same length.

14:18

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"0234567890112"

Input

"01234"

Input

"12345"

Your code is saved on this device.Solution