gistfile1.py

"""
Test:
  Given two strings, `a` and `b`. Sort the letters in `a` by the order of letters in `b`.
  For example:
    a = "ssttexeste"
    b = "test"
    result = "ttteeesssx"
"""

from collections import defaultdict

def a_by_b(a, b):
    # Build a dict f of letter frequencies in a.
    f = defaultdict(int)
    for c in a:
        f[c] += 1

    # Run through the chars in b.
    r = ''
    for c in b:
        if c in f:
            r += (c * f[c])
            f[c] = 0

    # Any leftovers.
    for c, n in f.iteritems():
        if n > 0:
            r += (c * f[c])

    return r

def test():
    a = "adlkfhxaxjxkxhxfwkhkjfhjkahjksedeheflhadslfkhdfjkadhjhdhskghdjdjkhskkhjokhkshakhlhfkjdshjfkshhkskskss"
    b = "alskdjfhg"
    r = a_by_b(a, b)

    s = r[:len("aaaaaallllssssssssssskkkkkkkkkkkkkkkkkkkkdddddddddjjjjjjjjjjjffffffffhhhhhhhhhhhhhhhhhhhhhg")]
    e = r[len("aaaaaallllssssssssssskkkkkkkkkkkkkkkkkkkkdddddddddjjjjjjjjjjjffffffffhhhhhhhhhhhhhhhhhhhhhg"):]
    assert r.startswith(s)  # Check the sorted start.
    assert sorted(e) == ['e'] * 3 + ['o'] + ['w'] + ['x'] * 5  # Check the remaining chars aren't dropped.

if __name__ == '__main__':
    test()

Nice. Has the same complexity as the build index then sort approach though, ie, 2 * n log n.

That's the approach that I took, @ssadler: https://gist.github.com/icio/6191f2ce019c9c795a30. Can you explain your derivation of the complexity?

Yea, it's pretty shit... Building an index, or creating a counter, has n log n complexity. Doing it twice is 2 n log n. But since we have 2 inputs, the above solution is actually more like.... n log n + m log n or whatever...

How bout this:

sorted("ccbbaae", key="abc".find)

also, did you see: https://gist.github.com/ssadler/6842183