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.
This approach involves rearranging the string using the modulo operation to handle the cyclic nature of the problem. For each character, we find its new position by moving k steps forward, accounting for any wrap-arounds using modulo division.
This C implementation initializes a new array for the encrypted string. It uses a loop to calculate each character's new position using modulo to correctly cycle through the string, then assigns the character to the appropriate index.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the encrypted string.
This approach modifies the original string by rotating segments of it in place. We use slicing to concatenate segments of the string in the correct order, a technique viable due to the small size constraint of the input.
In Python, we utilize string slicing to achieve the rotation. We adjust k via modulus to handle cases where k exceeds the string length, returning the desired segments rearranged.
Python
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as a new string is created for the result.
We can use the simulation method. For the i^{th} character of the string, we replace it with the character at position (i + k) bmod n of the string.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Cyclic Reordering with Modulo | Time Complexity: O(n), where n is the length of the string. |
| Rotation with In-place Modification | Time Complexity: O(n), where n is the length of the string. |
| Simulation | — |
| 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 |
LeetCode 3210 - Find ENCRYPTED string #coding #computerscience #programming #leetcode #python • Comp&Beyond • 429 views views
Watch 8 more video solutions →Practice Find the Encrypted String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor