append strings with increasing frequency

user_13518126 0
Viewed 233

You are given two strings S and T. An infinitely long string is formed in the following manner:

  • Take an empty string,
  • Append S one time,
  • Append T two times,
  • Append S three times,
  • Append T four times,

and so on, appending the strings alternately and increasing the number of repetitions by 1 each time.

You will also be given an integer K.
You need to tell the Kth Character of this infinitely long string.

Sample Input (S, T, K):

a
bc
4

Sample Output:

b

Sample Explanation: The string formed will be "abcbcaaabcbcbcbcaaaaa...". So the 4th character is "b".

My attempt:

public class FindKthCharacter {

    public char find(String S, String T, int K) {
        // lengths of S and T
        int s = S.length();
        int t = T.length();
        // Counters for S and T
        int sCounter = 1;
        int tCounter = 2;
        // To store final chunks of string
        StringBuilder sb = new StringBuilder();
        // Loop until K is greater than zero
        while (K > 0) {
            if (K > sCounter * s) {
                K -= sCounter * s;
                sCounter += 2;
                if (K > tCounter * t) {
                    K -= tCounter * t;
                    tCounter += 2;
                } else {
                    return sb.append(T.repeat(tCounter)).charAt(K - 1);
                }
            } else {
                return sb.append(S.repeat(sCounter)).charAt(K - 1);
            }
        }
        return '\u0000';
    }
}

But is there any better way to reduce its time complexity?

algorithm java
3 Answers

Here my quick attempt, there probably is a better solution. Runtime is still O(sqrt n), but memory is O(1).

public static char find(String a, String b, int k) {
    int lenA = a.length();
    int lenB = b.length();

    int rep = 0;
    boolean isA = false;
    while (k >= 0) {
        ++rep;
        isA = !isA;
        k -= (isA ? lenA : lenB) * rep;
    }
    int len = (isA ? lenA : lenB);
    int idx = (len * rep + k) % len;
    return (isA ? a : b).charAt(idx);
}
user_104048540

I've tried to give a guide here, rather than just give the solution.

If s and t are the lengths of the strings S and T, then you need to find the largest odd n such that (1+3+5+...+n)s + (2+4+6+...+(n+1))t < K.

You can simplify these expressions to get a quadratic equation in n.

Let N be (1+3+..+n)s + (2+4+6+...+(n+1))t. You know that K will lie either in the next (n+2) copies of S, or the (n+3) copies of T that follow. Compare K to N+(n+2)s, and take the appropriate letter of either S or T using a modulo.

The only difficult step here is solving the large quadratic, but you can do it in O(log K) arithmetic operations easily enough by doubling n until it's too large, and then using a binary search on the remaining range. (If K is not too large so that floating point is viable, you can do it in O(1) time using the well-known quadratic formula).

user_14007930

Here's a O(1) solution that took me some time to come up with (read I would have failed an interview on time). Hopefully the process is clear and you can implement it in code.

Our Goal is to return the char that maps to the kth index. But How? Just 4 easy steps, actually.

Step 1: Find out how many iterations of our two patterns it would take to represent at least k characters.

Step 2: Using this above number of iterations i, return how many characters are present in the previous i-1 iterations.

Step 3: Get the number of characters n into iteration i that our kth character is. (k - result of step 2)

Step 4: Mod n by the length of the pattern to get index into pattern for the specific char. If i is odd, look into s, else look into t.

For step 1, we need to find a formula to give us the iteration i that character k is in. To derive this formula, it may be easier to first derive the formula needed for step 2.

Step 2's formula is basically given an iteration i, return how many characters are present in that iteration. We are solving for 'k' in this equation and are given i, while it's the opposite for step 1 where were are solving for i given k. If we can derive the equation of find k given i, then we can surely reverse it to find i given k.

Now, let's try to derive the formula for step 2 and find k given i. Here it's best to start with the most basic example to see the pattern.

s = "a", t = "b"

i=1 a
i=2 abb
i=3 abbaaa
i=4 abbaaabbbb
i=5 abbaaabbbbaaaaa
i=6 abbaaabbbbaaaaabbbbbb

Counting the total number of combined chars for each pattern during its next iteration gives us:

#iterations of pattern: 1  2  3  4   5   6   7   8   9   10
every new s iteration:  1, 4, 9, 16, 25, 36, 49, 64, 81, 100
every new t iteration:  2, 6, 12, 20, 30, 42, 56, 72, 90, 110

You might notice some nice patterns here. For example, s has a really nice formula to find out how many combined characters it has at any given iteration. It's simply (# of s iterations^2)*s.length. t also has a simple formula. It is (# of t iterations * (# of t iterations + 1))*t.length. You may have noticed that these formulas are the formulas for sum of odd and even numbers (if you did you get a kudos). This makes sense because each pattern's sum for an iteration i is the sum of all of its previous iterations.

Using s,t as length of their respective patterns, we now have the following formula to find the total number of chars at a given iteration.

#chars = s*(# of s iterations)^2 + t * (# of t iterations * (# of t iterations + 1))

Now we just need to do some math to get the number of iterations for each pattern given i.

# of s iterations given i = ceil(i/2.0)
# of t iterations given i = floor(i/2) which / operation gives us by default

Plugging these back into our formula we get: total # of chars = s*(ceil(i/2.0)^2) + t*((i/2)*((i/2)+1))

We have just completed step 2, and we now know at any given iteration how many total chars there are. We could stop here and start picking random iterations and adjusting accordingly until we get near k, but we can do better than that. Let's use the above formula now to complete step 1 which we skipped. We just need to reorganize our equation to solve for i now.

Doing some simplyfying we get:

    //      2
    //     i        i    i
    // s  (-)  + t  -  ( - + 1 ) = k
    //     2        2    2
    // ----------------------------
    //    2
    //   i     t    i
    // s -  +  -  ( - + 1 )i = k
    //   4     2    2
    // ----------------------------
    //     2        2
    //   si       ti       ti
    //  ----  +  ----  +  ---- - k = 0
    //   4        4        2
    // ----------------------------
    //          
    //    2     2     
    //  si  + ti  +  2ti - 4k = 0
    // ----------------------------
    //           2   
    //   (s + t)i  + 2ti - 4k = 0
    // ----------------------------

This looks like a polynomial. Wow! You're right! That means we can solve it using the quadratic formula. A=(s+t), B=2t, C=-4k quadratic formula = (-2t + sqrt(2t^2 + 16(s+t)k)) / 2(s+t)

This is our formula for step 1, and it will give us the iteration that the kth character is on. We just need to ceil it. I'm actually not smart enough to know why this works. It just does. Here is a desmos graph that graphs our two polynomials from step 2: s(Siterations)^2 and t(Titerations (Titerations + 1)). The area under both curves is our total number of chars at an iteration (the vertical line). The formula from step 1 is also graphed, and we can see that for any s, t, k that the x intercept (which represents our xth iteration) is always: previous iteration < x <= current iteration, which is why the ceil works.

We have now completed steps 1 and 2. We have a formula to get the ith iteration that the kth character is on and a formula that gives us how many characters are in an ith iteration. Steps 3 and 4 should follow and we get our answer. This is constant time.

user_167755140
Related