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

#### Bydinesh

Apr 30, 2022

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.

GD Star Rating

Source