Ramblings on Programming

  • Variation of Dutch National Flag Problem
    Question
    You are given a string that only contains upper case letters , blanks and lower case letters. Think of an algorithm that,
    Lets all the lowercase letters be located at the beginning of the string and uppercase letters be located at the end of the string, and the blanks be located in the middle.
    Constraint:The relative order of the upper case letters or the lowercase letters should not change.
    Solution
    1. Scan the string to find lengths of capital letters, space, and small letters sub-arrays. I will demonstrate things only for say small letters; lets say the length comes out to be k. I also have a look up table which has every alphabet starting from a maps to 1 and z maps to 26. Now I re-scan the string; for every small letter encountered I know its exact position in the small letter sub-array so I can calculate a some kind of 26 base value for the small letter string as: a*26^(k-1) + z*26(^k-2) +…+ p*26^(0) (if a, z, …p is the order of appearance in the original string) This step is O(k) i.e. O(n) by using a small trick (Scan the input string in reverse order; and store at any point the partial sum and the value 26^j; this will help in adding the next value as partial sum + 26*26^j. We do this because if you work from start of string instead of reverse calculating 26^j takes log j base 26 time.) Lets say the sum comes out to be S.
    2. Now our problem comes to finding the small letter array corresponding to S similar to computing bit array corresponding to a decimal number.This should take O(log S base 26) = O(k) (similar to time complexity of calculating bit array from decimal i.e. log n base 2) (here I have assumed that division operation takes O(1) ).Push every small letter output into the original string.