Input is two strings, the first string being the long string and the second smaller string being the permuted string.
The output should return the starting indices of all occurrences as well as the permutation of the substring in the longer string.
Case 1)
permutationsInString('abcdcbadefbac', 'abc')
sample output: { '0': 'abc', '4': 'cba', '10': 'bac' }
Case 2)
permutationsInString('abcabacba', 'abc')
sample output: { '0': 'abc',
'1': 'bca',
'2': 'cab',
'4': 'bac',
'5': 'acb',
'6': 'cba' }
Case 3)
permutationsInString('a', 'abc')
sample output: {}
My solution is Naive and Brute Force, was wondering if there are any other possible ways to reduce the time and space complexity.
function permutationsInString(longString, shortString) {
let hash = {}; // let hash store the resulting found permutation strings and their respective index in the long string
let permutations_shortStrings = permutationArr(shortString) ; // permute the short string and store the values in an array called permutations_shortStrings
for(let i = 0 ; i < permutations_shortStrings.length ; i++) { // iterate through the array of permutations to check if the long string contains any of the values
if(longString.indexOf(permutations_shortStrings[i]) !== -1) // need to check for -1 as it indicates the substring cannot be found
hash[longString.indexOf(permutations_shortStrings[i])] = permutations_shortStrings[i];
}
return hash ;
}
function permutationArr(str)
{
var arr = str.split(''),
permutations = [];
function swap(a, b)
{
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
// Heap's algorithm implementation
function generate(n) {
if (n == 1) {
permutations.push(arr.join().replace(/,/g, ''));
} else {
for (var i = 0; i < n; ++i) {
generate(n - 1);
swap(n % 2 ? 0 : i, n - 1);
}
}
}
generate(arr.length);
return permutations;
}
