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 Solution

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 a naive solution to generate all permutations of a string would be at least exponential, specifically O(n!), where n is the length of the string. This is because there are n! (n factorial) possible permutations of a string with n characters. For example, a string with 4 characters has 4! = 24 permutations, and a string with 5 characters has 5! = 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'
  ]

This time complexity is not very efficient, especially for larger strings, as the number of permutations grows very quickly with the size of the string. There are more efficient algorithms for generating permutations that have a lower time complexity, such as the Heap’s algorithm, which has a time complexity of O(n * n!), or the Steinhaus–Johnson–Trotter algorithm, which has a time complexity of O(n * n). These algorithms may be more suitable for generating permutations of larger strings.

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