Skip to content

3210. Find the Encrypted String

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

Solutions

Solution 1: Simulation

Thinking

\(n\le 100\), so we can replace each character by the one \(k\) steps ahead. \(k\) may reach \(10^4\), so stepping \(k\) times would wrap many times, yet a cyclic shift depends only on \(k\bmod n\).

Write \(s[(i+k)\bmod n]\) into a new string for every \(i\). One linear pass builds the answer without rotating \(k\) rounds.

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\).

1
2
3
4
5
6
7
class Solution:
    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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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);
    }
}

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

1
2
3
4
5
6
7
func getEncryptedString(s string, k int) string {
    cs := []byte(s)
    for i := range s {
        cs[i] = s[(i+k)%len(s)]
    }
    return string(cs)
}

1
2
3
4
5
6
7
8
function getEncryptedString(s: string, k: number): string {
    const cs: string[] = [];
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        cs[i] = s[(i + k) % n];
    }
    return cs.join('');
}

Comments