Welcome to Subscribe On Youtube

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

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.

  • 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;
    }
}


  • 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;
    }
};


  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions