Scale Engineer

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 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:

  • For i = 0, the 3rd character after 'd' is 't'.
  • For i = 1, the 3rd character after 'a' is 'd'.
  • For i = 2, the 3rd character after 'r' is 'a'.
  • For 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 <= 100
  • 1 <= k <= 104
  • 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:

    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

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.

Solutions

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 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 →

Next problem