Find the Encrypted String

Easy

#2851Time: O(n), where `n` is the length of the string `s`. In Java, `substring()` and string concatenation operations each create new strings and copy characters, taking time proportional to the string length.Space: O(n). This approach creates intermediate substrings and a final result string, all of which require space proportional to `n`.

Data structures

String

Prompt

You are given a string s and an integer k. Encrypt the string using the following algorithm:

For each character c in s, replace c with the k^th character after c in the string (in a cyclic manner).

Return the encrypted string.

Example 1:

Input: s = "dart", k = 3

Output: "tdar"

Explanation:

For i = 0, the 3^rd character after 'd' is 't'.
For i = 1, the 3^rd character after 'a' is 'd'.
For i = 2, the 3^rd character after 'r' is 'a'.
For i = 3, the 3^rd 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 <= 100
1 <= k <= 10⁴
s consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach recognizes that the described encryption algorithm is equivalent to a left circular shift (or rotation) of the string. The encrypted string can be constructed by splitting the original string at the k-th position (cyclically) and concatenating the two resulting parts in reverse order.

Algorithm

Let n be the length of the input string s.
The rotation is cyclic, so rotating by k is identical to rotating by k % n. Calculate the effective rotation amount, rot = k % n.
A left rotation by rot positions means the substring starting at index rot becomes the new prefix of the string.
This new prefix is s.substring(rot).
The original prefix of the string, s.substring(0, rot), becomes the new suffix.
Concatenate these two parts: s.substring(rot) + s.substring(0, rot) to get the final encrypted string.

Walkthrough

The core idea is to treat the encryption as a string rotation problem, which can be solved efficiently using substring operations.

Algorithm:
1. Let n be the length of the input string s.
2. The rotation is cyclic, so rotating by k is identical to rotating by k % n. Calculate the effective rotation amount, rot = k % n.
3. A left rotation by rot positions means the substring starting at index rot becomes the new prefix of the string.
4. This new prefix is s.substring(rot).
5. The original prefix of the string, s.substring(0, rot), becomes the new suffix.
6. Concatenate these two parts: s.substring(rot) + s.substring(0, rot) to get the final encrypted string.

Code Snippet:

1class Solution {2    public String getEncryptedString(String s, int k) {3        int n = s.length();4        int rot = k % n;5        String rightPart = s.substring(rot);6        String leftPart = s.substring(0, rot);7        return rightPart + leftPart;8    }9}

Complexity

Time

O(n), where `n` is the length of the string `s`. In Java, `substring()` and string concatenation operations each create new strings and copy characters, taking time proportional to the string length.

Space

O(n). This approach creates intermediate substrings and a final result string, all of which require space proportional to `n`.

Trade-offs

Pros

Code is very concise and easy to understand.
Effectively uses high-level, built-in string manipulation functions.

Cons

Can be slightly less performant than manual construction. It involves creating at least two intermediate string objects before the final result, leading to extra memory allocations and character copying.

This approach directly implements the logic described in the problem statement. It iterates through each index of the target encrypted string and calculates the corresponding character from the source string using the cyclic shift formula. A StringBuilder is used for efficient string creation.

Algorithm

Get the length of the string, n = s.length().
Initialize a StringBuilder with a capacity of n to avoid internal array resizing during appends.
Loop from i = 0 to n - 1. The variable i represents the index in the new encrypted string.
For each index i, the problem states the new character is the k-th character after the character at index i. This means the source character is at index (i + k).
To handle the cyclic nature, we use the modulo operator: sourceIndex = (i + k) % n.
Get the character from the original string at sourceIndex: s.charAt(sourceIndex).
Append this character to the StringBuilder.
After the loop, convert the StringBuilder to a String and return it.

Walkthrough

This method builds the resulting string character by character, which is often one of the most efficient ways to construct strings in Java.

Algorithm:
1. Get the length of the string, n = s.length().
2. Initialize a StringBuilder with a capacity of n to avoid internal array resizing during appends.
3. Loop from i = 0 to n - 1. The variable i represents the index in the new encrypted string.
4. For each index i, the problem states the new character is the k-th character after the character at index i. This means the source character is at index (i + k).
5. To handle the cyclic nature, we use the modulo operator: sourceIndex = (i + k) % n.
6. Get the character from the original string at sourceIndex: s.charAt(sourceIndex).
7. Append this character to the StringBuilder.
8. After the loop, convert the StringBuilder to a String and return it.

Code Snippet:

1class Solution {2    public String getEncryptedString(String s, int k) {3        int n = s.length();4        StringBuilder result = new StringBuilder(n);5        for (int i = 0; i < n; i++) {6            int sourceIndex = (i + k) % n;7            result.append(s.charAt(sourceIndex));8        }9        return result.toString();10    }11}

Complexity

Time

O(n), where `n` is the length of the string `s`. The code iterates through the string once. Operations inside the loop (`%`, `charAt`, `append`) are constant time (amortized for `append`).

Space

O(n). A `StringBuilder` is used, which internally allocates a character array of size `n` to build the result string.

Trade-offs

Pros

Generally more performant and memory-efficient as it avoids creating intermediate string objects.
Builds the final string in a single pass over the input data.

Cons

The code is slightly more verbose compared to the string slicing approach.

Solutions

Solution

1class Solution {2public3  String getEncryptedString(String s, int k) {4    char[] cs = s.toCharArray();5    int n = cs.length;6    for (int i = 0; i < n; ++i) {7      cs[i] = s.charAt((i + k) % n);8    }9    return new String(cs);10  }11}

1class Solution {2public:3  string getEncryptedString(string s, int k) {4    int n = s.length();5    string cs(n, ' ');6    for (int i = 0; i < n; ++i) {7      cs[i] = s[(i + k) % n];8    }9    return cs;10  }11};

1class Solution:2    def getEncryptedString(self, s: str, k: int) -> str: cs = list(s) n = len(s) for i in range(n): cs[i] = s[(i + k) % n] return "" . join(cs)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem