Teaching Kids Programming – Index Into an Infinite String (Find Substring)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given an alphabet (can be lower or uppercase) string s and two integers i and j where i < j. Let’s say p is an infinite string of s repeating forever. Return the substring of p from indexes [i, j).

Constraints
1 ≤ n ≤ 100,000 where n is the length of s
0 ≤ i < j < 2 ** 31
Example 1
Input
s = “tiger”
i = 6
j = 8
Output
“ig”

Example 2
Input
s = “hi”
i = 2
j = 6
Output
“hihi”

Try to keep the index within string size. (Use % operator)

Algorithms to Find the Substring of an Infinite String

We need to iterate over the indice range and then map it to the original string pattern using the % operator. We can’t store this infinite string into memory. We store the characters in a list, and then join them (concatenation) as a string.

1
2
3
4
5
6

class Solution:
    def solve(self, s, i, j):
        ans = []
        for x in range(i, j):
            ans.append(s[x % len(s)])
        return "".join(ans)

class Solution:
    def solve(self, s, i, j):
        ans = []
        for x in range(i, j):
            ans.append(s[x % len(s)])
        return "".join(ans)

This can be re-written into One Liner.

1
2
3

class Solution:
    def solve(self, s, i, j):
        return "".join(s[x % len(s)] for x in range(i, j))

class Solution:
    def solve(self, s, i, j):
        return "".join(s[x % len(s)] for x in range(i, j))

The result string has k = j – i characters, we can find the substring from a limited substring s*(k+1). The i index need to be mapped to the single string pattern. Then we return the substring with k letters after it.

1
2
3
4
5
6

class Solution:
    def solve(self, s, i, j):
        k = j - i
        i = i % len(s)
        p = s * (k + 1)
        return p[i : i + k]        

class Solution:
    def solve(self, s, i, j):
        k = j - i
        i = i % len(s)
        p = s * (k + 1)
        return p[i : i + k]        

All implementations have O(N) time and space complexity where N is the number of the characters to return i.e. j-i.

–EOF (The Ultimate Computing & Technology Blog) —