JS program to rotate a given String in specified direction by specified magnitude

Question

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]);
    }
  }
};

trincot · Accepted Answer

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
console.log(task18("linkinpark", "L 6 R 5 L 4")); // YES
console.log(task18("carrace", "L 2 R 2 L 3")); // NO
console.log(task18("pnesumonoultramicroscopicsilicovolcanoconiosisfloccinaucinihilipilification", "R9R1L4L9")); // YES

JS program to rotate a given String in specified direction by specified magnitude

Answers (2)

Related Questions