|
| 1 | +/** |
| 2 | + * Booth's Algorithm finds the lexicographically minimal rotation of a string. |
| 3 | + * Time Complexity: O(n) - Linear time where n is the length of input string |
| 4 | + * Space Complexity: O(n) - Linear space for failure function array |
| 5 | + * For More Visit - https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm |
| 6 | + *@example |
| 7 | + * Input: "baca" |
| 8 | + * All possible rotations: |
| 9 | + * - "baca" |
| 10 | + * - "acab" |
| 11 | + * - "caba" |
| 12 | + * - "abac" |
| 13 | + * Output: "abac" (lexicographically smallest) |
| 14 | + * |
| 15 | + * How it works: |
| 16 | + * 1. Doubles the input string to handle all rotations |
| 17 | + * 2. Uses failure function (similar to KMP) to find minimal rotation |
| 18 | + * 3. Maintains a pointer to the start of minimal rotation found so far |
| 19 | + *@param {string} str - Input string to find minimal rotation |
| 20 | + *@returns {string} - Lexicographically minimal rotation of the input string |
| 21 | + *@throws {Error} - If input is not a string or is empty |
| 22 | + */ |
| 23 | +exportfunctionfindMinimalRotation(str){ |
| 24 | +if(typeofstr!=='string'){ |
| 25 | +thrownewError('Input must be a string') |
| 26 | +} |
| 27 | + |
| 28 | +if(str.length===0){ |
| 29 | +thrownewError('Input string cannot be empty') |
| 30 | +} |
| 31 | + |
| 32 | +// Double the string for rotation comparison |
| 33 | +// This allows us to check all rotations by just sliding a window |
| 34 | +consts=str+str |
| 35 | +constn=s.length |
| 36 | + |
| 37 | +// Initialize failure function array |
| 38 | +constf=newArray(n).fill(-1) |
| 39 | +letk=0// Starting position of minimal rotation |
| 40 | + |
| 41 | +//Algorithm's implementation |
| 42 | +// Iterate through the doubled string |
| 43 | +// j is the current position we're examining |
| 44 | +for(letj=1;j<n;j++){ |
| 45 | +// i is the length of the matched prefix in the current candidate |
| 46 | +// Get the failure function value for the previous position |
| 47 | +leti=f[j-k-1] |
| 48 | +// This loop handles the case when we need to update our current minimal rotation |
| 49 | +// It compares characters and finds if there's a better (lexicographically smaller) rotation |
| 50 | +while(i!==-1&&s[j]!==s[k+i+1]){ |
| 51 | +// If we find a smaller character, we've found a better rotation |
| 52 | +// Update k to the new starting position |
| 53 | +if(s[j]<s[k+i+1]){ |
| 54 | +// j-i-1 gives us the starting position of the new minimal rotation |
| 55 | +k=j-i-1 |
| 56 | +} |
| 57 | +// Update i using the failure function to try shorter prefixes |
| 58 | +i=f[i] |
| 59 | +} |
| 60 | + |
| 61 | +// This block updates the failure function and handles new character comparisons |
| 62 | +if(i===-1&&s[j]!==s[k+i+1]){ |
| 63 | +// If current character is smaller, update the minimal rotation start |
| 64 | +if(s[j]<s[k+i+1]){ |
| 65 | +k=j |
| 66 | +} |
| 67 | +//If no match found,mark failure function accordingly |
| 68 | +f[j-k]=-1 |
| 69 | +}else{ |
| 70 | +//If match found, extend the matched length |
| 71 | +f[j-k]=i+1 |
| 72 | +} |
| 73 | +} |
| 74 | +// After finding k (the starting position of minimal rotation): |
| 75 | +// 1. slice(k): Take substring from position k to end |
| 76 | +// 2. slice(0, k): Take substring from start to position k |
| 77 | +// 3. Concatenate them to get the minimal rotation |
| 78 | +returnstr.slice(k)+str.slice(0,k) |
| 79 | +} |