Find All Short String Permutations in a Longer String

Given a short string A and a longer string B. Find all permutations of A that occur on B. We assume that both strings contain only ASCII characters.

For example:

A = “abcd”

B = “cdababcdeedcba”

Reslut = [“cdab”, “abcd”, “dcba”]

Brute Force Solutoin

procdure getAllPermutations(a, b)
1. permutations = [] // array of all a permutations
2. result = [] // empty array
3. for i = 0 to b.length
   A. if permutations index of b.substring(i, a.length) > -1
      A.1 push b.substring(i, a.length) to result
4 return result

JavaScript Implementation

The time complexity of this naive solution would be at least exponentialO(an, b) after we drop the constants. The example above “abcd” has 24 permutations, adding another character to it will give as 120 permutations.

    'abcd', 'abdc', 'acbd',
    'acdb', 'adbc', 'adcb',
    'bacd', 'badc', 'bcad',
    'bcda', 'bdac', 'bdca',
    'cabd', 'cadb', 'cbad',
    'cbda', 'cdab', 'cdba',
    'dabc', 'dacb', 'dbac',
    'dbca', 'dcab', 'dcba'

Try to run this JS implementation where a.length >= 10, and you’ll probably get a timeout error.

Optimized Algorithm

To optimize our algorithm we could implement something similar to the Rabin-Karp algorithm. As with many exponential runtimes’ algorithms, such as the famous Fibonacci sequence algorithm, we could improve it by implementing a hash table.

Mathematical Background

Let S = {A_1, …, A_n} be a multiset list of size N that contains only prime numbers. Let the sum of the numbers in S equal some integer Q. Then S is the only possible entirely prime multiset of size N, whose elements can sum to Q.

Ephraim Rotchild

This allows us to assign each character to a prime number, where the prime number is the hash key, the sum of all permutations of the shorter string characters keys are equal. Now the only thing left is to check if the sum of substrings on the longer string is equal to the sum of the sorter string.

Pseudocode Implementation

procedure getAllPermutations(a, b)
1. result = []
2. smallHash = primes[a[0]] + primes[a[1]] ... + primes[a[a.length]]
3. left = 0, right = shorter.length
4. currentHash = primes[a[0]] + primes[a[1]] ... + primes[a[a.length]]
5. while right <= b.length
   A. if currentHash == smallHash
      A1. result.append(longer.substring(left, right))
   B. currentHash -= primes[b.charAt(left++)]
   C. if right < b.length
      C1. currentHash += primes[b.charAt(right)]
   D. right++
6. return result

Dropping the constants, we get it done on linear time – O(b). Note that the constants, in this case, can have a significant influence on the performance of the algorithm, but anyway, the performance of this algorithm will be much better than our naive algorithm.

JavaScript Implementation


Leave a comment

Your email address will not be published.