Find the Encrypted String

EASY

Description

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

Checkout 2 different approaches to solve Find the Encrypted String. Click on different approaches to view the approach and algorithm in detail.

String Slicing and Concatenation

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.

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:

class Solution {
    public String getEncryptedString(String s, int k) {
        int n = s.length();
        int rot = k % n;
        String rightPart = s.substring(rot);
        String leftPart = s.substring(0, rot);
        return rightPart + leftPart;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(n). This approach creates intermediate substrings and a final result string, all of which require space proportional to `n`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find the Encrypted String. Click on different languages to view the code.

class Solution {
public
  String getEncryptedString(String s, int k) {
    char[] cs = s.toCharArray();
    int n = cs.length;
    for (int i = 0; i < n; ++i) {
      cs[i] = s.charAt((i + k) % n);
    }
    return new String(cs);
  }
}

Video Solution

Watch the video walkthrough for Find the Encrypted String

Data Structures:

String