# JS Program To Rotate A Given String In Specified Direction By Specified Magnitude

## 14 May 2020 - 1 answer

function must take two string arguments: one, a string which is to be rotated and the second string denoting any number of rotations in a particular direction with specific magnitudes. The second string is in the form of : X a X b X c ....... Where X denotes the direction of rotataion which is either L or R. a,b,c... are integers which denotes the magnitude (not more than 9) of the direction which is in their left side.

For example, if these are the arguments : ("abcde","L 3 R 2 R 4") The ouput would be YES

Explanation:

• Here, number of rotations are 3.
• After applying first rotation L 3, the string is: 'deabc'. Here, the first character is 'd'
• After applying second rotation R 2, the string is: 'bcdea'. Here, the first character is 'b'
• After applying third rotation R 4, the string is: 'cdeab'. Here, the first character is 'c'

Thus, after all the rotations the FIRSTCHARSTRING string will be "dbc" which is an anagram of a sub string of original string "abcde".

here is what i tried but not getting anywhere

``````
const task18 = (str1, str2) => {
let count;
for (let i in str2) {
if (str2[i] === "L") {
let ans = str1.substring(str2[i + 1]) + str1.substring(0, str2[i + 1]);
count = ans[0];
return ans;
} else {
return str1.substring(str1, str1.length - str2[i + 1]);
}
}
};
``````

Several issues:

• you always exit the loop in the first iteration (with `return`).
• the last call of `substring` has a string as first argument, while a number is expected.
• `count = ans[0];` is taking the count from the wrong place. It is to be retrieved from `str2`, not `ans`.
• There is nothing that attempts to find whether the anagram is matching
• The function attempts to return part of `str1`, but the assignment is to return "YES" or "NO".

The easy part is the rotation. In fact it is not necessary to really rotate `str1`. It is much more efficient to just point with an index to what would be the start of the string after the rotation.

The difficult part is to find out whether the constructed string is an anagram of a substring of `str1`. The difficulty is that some characters in `str1` may be duplicate, and so an attempt to match could fail when you select the wrong one among the duplicate letters. This can be solved by using recursion and backtracking to attempt using one character among the duplicates, and then the next, until you have success, or all attempts fail.

There are some additional measures you could take to improve the running time: when the rotation string has more rotations than there are characters in `str1`, you can already return "NO".

If the rotations bring about a string that uses a certain character more that it occurs in `str1` (because a certain character position was revisited through rotations), then also you can return "NO".

For the recursive part, you could first look for the character that occurs the least in `str1`, so that you don't have to retry many times with another occurrence. Also you can track how far apart the matching characters are in `str1`: if they get too far apart (further than the total size of the substring), there is no use in continuing in that direction.

All this is implemented below:

``````function task18(str, rotations) {
// convert second argument: extract single rotations and convert to signed offsets
rotations = rotations.replace(/R\s*/g, "-").match(/-?\d/g).map(Number);

// Make a naive check to exclude rotation strings that are too long
if (rotations.length > str.length) return "NO"; // too many characters will be selected

// Register at which indexes a character occurs (as there may be duplicate characters)
let occurrences = Object.fromEntries(Array.from(str, c => [c, []]));
Array.from(str, (c, i) => occurrences[c].push(i));
// Count characters in str so to be able to detect a "NO" sooner.
let available = Object.fromEntries(Array.from(str, c => [c, occurrences[c].length]));

// Don't actually rotate the string, but maintain a current index
let current = 0;
let result = []; // The selected characters
for (let rot of rotations) {
let c = str[current = (current + str.length + rot) % str.length];
if (!available[c]--) return "NO"; // too many of the same character
result.push(c);
}

// Reorder characters, so those which have the least available occurrences
//  in the input string come first.
// This will optimise the depth first search for an anagram.
result.sort((a, b) => available[a] - available[b]);

// Perform a depth-first search for an anagram match
return (function dfs(i=0, first=str.length, last=-1) {
// first/last are the extreme indexes in str that have been matched
if (last - first >= result.length) return false; // subsequence will have gaps; backtrack
if (i >= result.length) return true; // all characters are allocated in a subsequence
let c = result[i];
let occ = occurrences[c];
let usedoccurrences = occ.length - available[c];
for (let j = 0; j <= available[c]; j++) {
if (dfs(i+1, Math.min(first, occ[j]), Math.max(last, occ[j+usedoccurrences-1]))) {
return true;
}
}
return false; // backtrack
})() ? "YES" : "NO"; // immediately invoke dfs: returns a boolean
}

// Test cases
console.log(task18("abcde","L 3 R 2 R 4")); // YES