Algorithms to Compute the Fibonacci String Sequence

Given strings s0, s1 and a positive integer n, return the nth term of the sequence A where:

A[0] = s0
A[1] = s1
A[n] = A[n – 1] + A[n – 2] if n is even, otherwise A[n] = A[n – 2] + A[n – 1].

For example, given s0 = “a” and s1 = “b”, the sequence A would be:
“a”
“b”
“ba” (“b” + “a”)
“bba” (“b” + “ba”)
“bbaba” (“bba” + “ba”)

Example 1
Input
s0 = “et”
s1 = “r”
n = 0
Output
“et”

Example 2
Input
s0 = “a”
s1 = “p”
n = 1
Output
“p”

Example 3
Input
s0 = “zs”
s1 = “v”
n = 3
Output
“vvzs”

Example 4
Input
s0 = “dx”
s1 = “a”
n = 4
Output
“aadxadx”

Recursive Fibonacci String Algorithm

The most intuitive implementation would be just implementing it in Recursion which just basically translates the definition:

1
2
3
4
5
6
7
8

string FibString(string s0, string s1, int n) {
    if (n == 0) return s0;
    if (n == 1) return s1;
    if (n & 1) {
        return solve(s0, s1, n - 2) + solve(s0, s1, n - 1);
    }
    return solve(s0, s1, n - 1) + solve(s0, s1, n - 2);
}

string FibString(string s0, string s1, int n) {
    if (n == 0) return s0;
    if (n == 1) return s1;
    if (n & 1) {
        return solve(s0, s1, n - 2) + solve(s0, s1, n - 1);
    }
    return solve(s0, s1, n - 1) + solve(s0, s1, n - 2);
}

However, this approach is inefficient (similar to Fibonacci numbers) – the algorithm has exponential complexity.

Recursive Fiboancci String Algorithm with Memoization

We can employ a hash table (Memoization) to remember the intermediate results – so every F(n) will only be computed once and stored in the table as a cache.

1
2
3
4
5
6
7
8
9
10
11
12
13

string FibString(string s0, string s1, int n) {
    unordered_map<int, string> memo;
    function<string(int)> A = [&](int n) {
        if (n == 0) return s0;
        if (n == 1) return s1;
        if (memo.count(n)) return memo[n];
        if (n & 1) {
            return memo[n] = A(n - 2) + A(n - 1);
        }
        return memo[n] = A(n - 1) + A(n - 2);
    };
    return A(n);
}

string FibString(string s0, string s1, int n) {
    unordered_map<int, string> memo;
    function<string(int)> A = [&](int n) {
        if (n == 0) return s0;
        if (n == 1) return s1;
        if (memo.count(n)) return memo[n];
        if (n & 1) {
            return memo[n] = A(n - 2) + A(n - 1);
        }
        return memo[n] = A(n - 1) + A(n - 2);
    };
    return A(n);
}

The above Fibonacci string algorithm has O(N) linear complexity and O(N) space complexity.

Iterative Algorithm to Compute the Fibonacci Strings

Like Fibonacci Numbers, we can also implement this in most efficient (in both time and space) manner.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public:
    string FibString(string s0, string s1, int n) {
        int i = 0;
        while (n--) {
            string ans = i++ % 2 ? s0 + s1 : s1 + s0;
            s0 = s1;
            s1 = ans;
        }
        return s0;
    }
};

class Solution {
    public:
    string FibString(string s0, string s1, int n) {
        int i = 0;
        while (n--) {
            string ans = i++ % 2 ? s0 + s1 : s1 + s0;
            s0 = s1;
            s1 = ans;
        }
        return s0;
    }
};

The above Algorithm has O(N) linear complexity and the space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —