Algorithms to Compute the SubString with Indexing into an Infinite String

You are given a 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).

Example 1
Input
s = “tiger”
i = 6
j = 8

Output
“ig”

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

Output
“hihi”

Index into Infinite String with 3 Parts

We can divide the [i:j) range into 3 parts: s[a:],s*t, and s[:b] where we need to figure out the values of a, t and b.

string solve(string s, int i, int j) {
    int n = s.size();
    int t = i / n;
    i = i % n;
    j -= t * n;
    string ans = s.substr(i, j - i);
    if (j > n) {
        t = (j - n) / n;
        j = (j - n) - t * n;
        while (t --) {
            ans += s;
        }
        ans += s.substr(0, j);
    }
    return ans;
}

However, this method is error-prone and especially with the index calculation which may go wrong.

Compute the Corresponding Index from Infinite

We can compute directly the index which is a lot simpler:

string solve(string s, int i, int j) {
    int n = s.size();
    string ans = "";
    for (int k = i; k < j; ++ k) {
        ans += s[k % n];
    }
    return ans;
}

This is a much cleaner method.

–EOF (The Ultimate Computing & Technology Blog) —