Skip to content

3817. Good Indices in a Digit String πŸ”’

Description

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 <= 105
  • s only consists of digits from '0' to '9'.

Solutions

Solution 1: Simulation

Thinking

Index \(i\) is good iff some substring ending at \(i\) equals the decimal writing of \(i\). \(|s| \le 10^5\), yet that writing has length at most \(6\).

For each \(i\) it suffices to compare a suffix of length \(|\mathrm{str}(i)|\); other substrings cannot match.

We scan every index and test \(s[i+1-k:i+1]\) against \(\mathrm{str}(i)\).

The total comparison work is linear in \(n\).

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 time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\), ignoring the space required for the answer.

1
2
3
4
5
6
7
8
9
class Solution:
    def goodIndices(self, s: str) -> List[int]:
        ans = []
        for i in range(len(s)):
            t = str(i)
            k = len(t)
            if s[i + 1 - k : i + 1] == t:
                ans.append(i)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public List<Integer> goodIndices(String s) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            String t = String.valueOf(i);
            int k = t.length();
            if (s.substring(i + 1 - k, i + 1).equals(t)) {
                ans.add(i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> goodIndices(string s) {
        vector<int> ans;
        for (int i = 0; i < s.size(); i++) {
            string t = to_string(i);
            int k = t.size();
            if (s.substr(i + 1 - k, k) == t) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func goodIndices(s string) (ans []int) {
    for i := range s {
        t := strconv.Itoa(i)
        k := len(t)
        if s[i+1-k:i+1] == t {
            ans = append(ans, i)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function goodIndices(s: string): number[] {
    const ans: number[] = [];
    for (let i = 0; i < s.length; i++) {
        const t = String(i);
        const k = t.length;
        if (s.slice(i + 1 - k, i + 1) === t) {
            ans.push(i);
        }
    }
    return ans;
}

Comments