#3210

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Find the Encrypted String

In this problem, you need to encrypt a string by shifting each character's position based on a given integer value.

Problem Statement

You are given a string s and an integer k. The task is to encrypt the string by shifting each character's position according to the formula (i + k) % s.length where i is the original index of each character. You need to return the new encrypted string after applying the shifting operation to each character in s.

For example, if s = "dart" and k = 3, the output will be the string "tdar" after shifting each character by 3 positions in a circular manner. If s = "aaa" and k = 1, the encrypted string will remain unchanged as "aaa".

Examples

Example 1

Input: s = "dart", k = 3

Output: "tdar"

Example 2

Input: s = "aaa", k = 1

Output: "aaa"

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.

Solution Approach

Index Calculation

To solve the problem, you must calculate the new index for each character using (i + k) % s.length. This formula ensures that the indices are wrapped around the string in case the value of k exceeds the length of the string.

String Construction

After determining the new indices, build the encrypted string by assigning each character from s to its new position in a result string. This can be done iteratively or using an array for better performance.

Efficiency Considerations

Although the problem's constraints suggest a straightforward solution, consider the efficiency of your approach, especially when k is large. Using modulo arithmetic helps in reducing unnecessary computations when k is greater than the string's length.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the method used for building the new string. Typically, iterating through each character in the string gives an O(n) complexity, where n is the length of the string. The space complexity is also O(n) due to the space required for the new string or array.

What Interviewers Usually Probe

The candidate understands string manipulation techniques.
The candidate efficiently uses modulo arithmetic to handle large values of k.
The candidate demonstrates awareness of time and space complexities in string-driven solutions.

Common Pitfalls or Variants

Common pitfalls

Not using modulo to handle cases where k is greater than the string length, leading to incorrect results.
Failing to handle edge cases such as when all characters are the same or when the string length is 1.
Overcomplicating the solution by not optimizing for large values of k.

Follow-up variants

Shift characters based on different patterns or by using different encryption techniques.
Encrypt the string using a different shift amount for each character.
Handle cases where the string contains uppercase letters or non-alphabetic characters.

FAQ

What is the encryption pattern used in the "Find the Encrypted String" problem?

The encryption pattern involves shifting each character of the string based on the formula (i + k) % s.length, where i is the index of the character in the original string.

How do I handle large values of k in the "Find the Encrypted String" problem?

Use modulo arithmetic to reduce the value of k to a manageable size, as shifting by a value greater than the string length can be simplified with k % s.length.

What are the common mistakes to avoid in this problem?

Common mistakes include failing to use modulo arithmetic for large k, overcomplicating the solution, or not handling edge cases such as small strings or uniform character strings.

How does GhostInterview help with the "Find the Encrypted String" problem?

GhostInterview provides structured solutions and suggestions, ensuring you understand string manipulation, modulo operations, and performance considerations for solving this problem efficiently.

What time complexity should I expect for solving the "Find the Encrypted String" problem?

The time complexity is O(n), where n is the length of the string, as the solution involves iterating through each character to calculate its new position.

terminal

Solution

Solution 1: Simulation

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.

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)

Continue Practicing

#3211 generate binary strings without adjacent zeros #3213 construct string with minimum cost #3216 lexicographically smallest string after a swap