title: Find if String can be a sub sequence in another string
body: <p>This question is a variation of Longest common sub-sequence which I was asked in a recent coding competition. It is not about finding the longest common sub sequence. </p>
  
  <p>Consider a larger string s1 = <code>abaabbabcacc</code> and a smaller string s2 = <code>abc</code>. The power of a string is defined as repetition of each character of that string. So: </p>
  
  <ul>
  <li>s2 to power 1 is "abc"</li>
  <li>s2 to power 2 is "aabbcc" </li>
  <li>s3 to power 3 is "aaabbbccc" etc. </li>
  </ul>
  
  <p>Now the question asked is as follows: How can we find the largest power of a string <strong>s2</strong> such that it was a valid sub-sequence in <strong>s1</strong>. So in this case answer is 3 because:</p>
  
  <pre><code>s2 to power 3 = "aaabbbccc"
  s1 = "(a)b(aabb)a(bc)a(cc)"
  </code></pre>
  
  <p>The brute force algorithm seems straightforward: You start which power 1 and check if s2 to power 1 is sub-sequence of s1. You repeat until maximum power k to get time complexity of O(kn). </p>
  
  <p>A better approach would be to first find the largest power k possible and then do binary search to find the required output. This would work in O(n*log(k)). So I was wondering if there is any method of doing this is O(n). </p>
  
  <p>We can assume there are no memory constraints.</p>