**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) —

**GD Star Rating***loading…*

485 words**Last Post**: Teaching Kids Programming – Intersection of Multiple Arrays (Set and Counter) **Next Post**: Teaching Kids Programming – Square of a List using Two Pointer Algorithm