Microsoft Interview Question
Given a string and a pattern consisting of 'a's and 'b's check whether the string follows the pattern. Example: the string "catcatdogcatcat" follows the pattern "aabaa" bu substiting "a" as "cat" and "b' as "dog". Whereas the string "catdogcatcat" does not follow the pattern "aabaa" regardless of what is substituted for "a" and "b".
Interview Answer
Anonymous
Dec 14, 2020
O(n^2) solution: If the string substituted for "a" is a_string and its length is a_length and "b" is b_string and its length is b_length. Choose a_length and b_length such that the length of the pattern sums up to the length of the given string. Then take the first a_length characters from the string for "a" and calculate the string to be substituted for "b" accordingly.