Watch 9 video solutions for Find the Encrypted String, a easy level problem involving String. This walkthrough by Comp&Beyond has 429 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s and an integer k. Encrypt the string using the following algorithm:
c in s, replace c with the kth character after c in the string (in a cyclic manner).Return the encrypted string.
Example 1:
Input: s = "dart", k = 3
Output: "tdar"
Explanation:
i = 0, the 3rd character after 'd' is 't'.i = 1, the 3rd character after 'a' is 'd'.i = 2, the 3rd character after 'r' is 'a'.i = 3, the 3rd character after 't' is 'r'.Example 2:
Input: s = "aaa", k = 1
Output: "aaa"
Explanation:
As all the characters are the same, the encrypted string will also be the same.
Constraints:
1 <= s.length <= 1001 <= k <= 104s consists only of lowercase English letters.Problem Overview: You receive a string s and an integer k. Each character in the encrypted string comes from index (i + k) % n of the original string, where n is the length of s. The task is to construct the resulting string after this cyclic shift.
Approach 1: Cyclic Reordering with Modulo (Time: O(n), Space: O(n))
The direct solution builds a new string by iterating through every index i from 0 to n-1. For each position, compute the source index using (i + k) % n and append that character to the result. The modulo operation handles wrap‑around when the index exceeds the string length. This approach is straightforward, avoids complex pointer manipulation, and works in linear time because each character is processed exactly once. It relies on basic string traversal and modular arithmetic.
Approach 2: Rotation with In-place Modification (Time: O(n), Space: O(1))
The encryption rule effectively performs a left rotation of the string by k positions. Instead of creating a new string, you can rotate the characters in place using the classic three‑reversal technique. First normalize k using k % n. Reverse the first k characters, reverse the remaining n-k, then reverse the entire sequence. After these operations, the characters appear in the same order as the encrypted result. This method is useful when memory usage matters or when you want to practice in-place manipulation techniques common in array and string rotation problems.
Recommended for interviews: The cyclic modulo approach is usually what interviewers expect first because it directly follows the formula in the problem statement and clearly demonstrates understanding of cyclic indexing. Mentioning the in-place rotation variant shows deeper familiarity with string/array manipulation and space optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Cyclic Reordering with Modulo | O(n) | O(n) | Best for clarity and typical interview solutions; simple linear scan with direct indexing |
| Rotation with In-place Modification | O(n) | O(1) | When minimizing extra memory or demonstrating in-place rotation techniques |