3210. Find the Encrypted String

EasyString

Leetcode Link

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The given problem can be visualized as a simple string manipulation task, resembling a cyclic permutation or rotation. When iterating through the string, the goal is to determine what character should replace each current character in the original position. This is done using the cyclic nature of the problem, where we wrap around the string when the replacement index exceeds the string's length.

For each character at index i, calculate the new position (i + k) % n, where n is the string's length. This formula effectively implements the cyclic behavior by ensuring the index wraps around to the beginning of the string once it reaches the end. By applying this formula to each character and constructing a new string based on these indices, we achieve the desired encrypted string.

Solution Approach

The solution utilizes a straightforward simulation approach to achieve the task. Here's how it works:

Convert the string s to a list of characters, cs. This facilitates modifying characters at specified indices.
Determine the length of the string n to handle the circular indexing.
Iterate over each index i from 0 to n-1. For each character at index i, compute the new position as (i + k) % n. This formula ensures that when the index exceeds n, it wraps around to the beginning, due to the modulo operation.
Update the character in cs at index i to be the character from the original string s at the computed position (i + k) % n.
Finally, concatenate the list cs back into a string and return it as the encrypted string.

The core of this approach lies in using modular arithmetic to ensure that the character replacement respects the cyclic nature required by the problem.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example where we have the string s = "abcde" and k = 2. Our goal is to encrypt this string using the described cyclic permutation approach.

Convert the String to a List:
- Start by transforming the string s into a list of characters cs = ['a', 'b', 'c', 'd', 'e']. This allows us to easily modify each character.
Determine the Length:
- Find the length of the string n = 5. This value will be used for cyclic indexing with modulo operations.
Iterate Over Each Character:
- For each index i, calculate the new position (i + k) % n.
- Index 0:
  - Character is 'a'.
  - New position = (0 + 2) % 5 = 2.
  - Replace 'a' with the character at index 2, which is 'c'. So, cs[0] = 'c'.
- Index 1:
  - Character is 'b'.
  - New position = (1 + 2) % 5 = 3.
  - Replace 'b' with the character at index 3, which is 'd'. So, cs[1] = 'd'.
- Index 2:
  - Character is 'c'.
  - New position = (2 + 2) % 5 = 4.
  - Replace 'c' with the character at index 4, which is 'e'. So, cs[2] = 'e'.
- Index 3:
  - Character is 'd'.
  - New position = (3 + 2) % 5 = 0.
  - Replace 'd' with the character at index 0, which is 'a'. So, cs[3] = 'a'.
- Index 4:
  - Character is 'e'.
  - New position = (4 + 2) % 5 = 1.
  - Replace 'e' with the character at index 1, which is 'b'. So, cs[4] = 'b'.
Concatenate the List:
- Finally, concatenate the list cs back into a string. The encrypted string is 'cdeab'.

Thus, for the input s = "abcde" and k = 2, the encrypted string is 'cdeab'.

Solution Implementation

1class Solution:
2    def getEncryptedString(self, s: str, k: int) -> str:
3        # Convert the input string into a list of characters
4        chars = list(s)
5        # Determine the length of the string
6        n = len(s)
7      
8        # Iterate over each character in the string
9        for i in range(n):
10            # Apply the encryption shift using modulo to wrap around
11            chars[i] = s[(i + k) % n]
12      
13        # Convert the list of characters back into a string and return
14        return "".join(chars)
15

1class Solution {
2    // This method returns an encrypted version of the input string by shifting its characters.
3    public String getEncryptedString(String s, int k) {
4        // Convert the input string to a character array
5        char[] characterArray = s.toCharArray();
6        // Get the length of the character array
7        int length = characterArray.length;
8      
9        // Iterate over each character in the array
10        for (int i = 0; i < length; ++i) {
11            // Modify each character by shifting it 'k' positions using modular arithmetic
12            characterArray[i] = s.charAt((i + k) % length);
13        }
14      
15        // Convert the modified character array back to a string and return it
16        return new String(characterArray);
17    }
18}
19

1class Solution {
2public:
3    // Function to get the encrypted string by rotating it to the right by k positions
4    string getEncryptedString(string s, int k) {
5        int n = s.length(); // Get the length of the string
6        string result(n, ' '); // Initialize a string of the same length with placeholders
7
8        // Loop through each character in the original string
9        for (int i = 0; i < n; ++i) {
10            // Calculate the new position for each character after rotation
11            // and assign it to the result string
12            result[i] = s[(i + k) % n];
13        }
14
15        return result; // Return the encrypted string
16    }
17};
18

1// This function takes a string 's' and an integer 'k', and returns the string 's' encrypted by rotating it.
2function getEncryptedString(s: string, k: number): string {
3    // Array to store the encrypted characters
4    const encryptedChars: string[] = [];
5    // Length of the input string 's'
6    const length = s.length;
7  
8    // Iterate through each character in the string
9    for (let i = 0; i < length; ++i) {
10        // Calculate the new position for each character with a rotation
11        // Use modulo to wrap around if the index exceeds the string's length
12        encryptedChars[i] = s[(i + k) % length];
13    }
14  
15    // Join the characters into a single string to form the encrypted result
16    return encryptedChars.join('');
17}
18

Time and Space Complexity

The time complexity of the code is O(n) because it involves iterating over the string s of length n once, modifying each character according to its new position. The space complexity is O(n) as well, since a new list cs of the same length as s is being created to store the transformed characters before converting it back to a string.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: