Given an array of \(n\) elements, give a linear-time algorithm to rotate the string \(k\) positions. That is, if the array contains \(a_{0}, a_{1}, \ldots, a_{n-1}\), the rotated array is \(a_{k}, a_{k+1}, \ldots, a_{n-1}, a_{0}, \ldots, \mathrm{a}_{k-1}\). Use at most a constant amount of extra memory. Hint: Reverse three subarrays.