LeetCode 3210 - Find the Encrypted String

LeetCode Problem 3210

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to implement a custom string encryption algorithm. We are given a string s and an integer k. For each character in s, we need to replace it with the character that is k positions ahead in the string, in a cyclic manner. "Cyclic" means that if the index goes beyond the end of the string, we wrap around to the beginning.

The input s is a string of lowercase English letters with a length between 1 and 100. The integer k is between 1 and 10,000. The expected output is the string obtained after performing this cyclic shift for every character.

Important observations include the fact that the string length is relatively small (up to 100), but k can be much larger than the string length. This immediately suggests we need to handle large k by taking k % len(s) to avoid unnecessary computations. Edge cases that could cause naive implementations to fail include when all characters are the same, when k is a multiple of the string length, and when s has length 1.

Approaches

The brute-force approach would iterate over each character, calculate the index of the kth character ahead, and append it to the result. This works correctly but is inefficient if k is much larger than the length of the string because it performs unnecessary repeated shifts.

The optimal approach leverages modular arithmetic. Since the string is cyclic, moving k positions ahead is equivalent to moving k % n positions ahead, where n is the string length. By precomputing this shift and using simple index arithmetic, we can construct the encrypted string in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*k)	O(n)	Directly computes the kth character for each position, inefficient for large k
Optimal	O(n)	O(n)	Uses modular arithmetic to compute the new index efficiently

Algorithm Walkthrough

1. Compute the length n of the input string s.
2. Compute the effective shift as shift = k % n to handle cases where k is larger than the string length.
3. Initialize an empty list result to store the encrypted characters.
4. Iterate over each index i in the string:

a. Compute the new index as (i + shift) % n.

b. Append s[new_index] to the result list. 5. Join the list result into a single string. 6. Return the joined string as the encrypted result.

Why it works: Each character is shifted by the effective distance in a cyclic manner. Using modulo ensures that the indexing wraps around correctly. Since we process each character exactly once, the output string is correct and complete.

Python Solution

class Solution:
    def getEncryptedString(self, s: str, k: int) -> str:
        n = len(s)
        shift = k % n
        result = []
        for i in range(n):
            new_index = (i + shift) % n
            result.append(s[new_index])
        return ''.join(result)

The implementation first computes the effective shift. A loop iterates over each index in the string, calculating the new index after the shift using modular arithmetic. The characters at these indices are collected in a list, which is joined into the final encrypted string.

Go Solution

func getEncryptedString(s string, k int) string {
    n := len(s)
    shift := k % n
    result := make([]byte, n)
    for i := 0; i < n; i++ {
        newIndex := (i + shift) % n
        result[i] = s[newIndex]
    }
    return string(result)
}

In Go, we use a byte slice to collect the shifted characters since strings are immutable. The modulo operation ensures cyclic behavior. Finally, we convert the byte slice back to a string for the result.

Worked Examples

Example 1: s = "dart", k = 3

i	Original char	new_index	Encrypted char
0	d	(0+3)%4=3	t
1	a	(1+3)%4=0	d
2	r	(2+3)%4=1	a
3	t	(3+3)%4=2	r

Encrypted string = "tdar"

Example 2: s = "aaa", k = 1

i	Original char	new_index	Encrypted char
0	a	(0+1)%3=1	a
1	a	(1+1)%3=2	a
2	a	(2+1)%3=0	a

Encrypted string = "aaa"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once to compute the encrypted string.
Space	O(n)	An auxiliary list or slice of length n is used to store the result.

The complexity is efficient because we avoid unnecessary repeated shifts by using modulo, and the input size is small enough that O(n) is perfectly acceptable.

Test Cases

# Provided examples
assert Solution().getEncryptedString("dart", 3) == "tdar"  # cyclic shift
assert Solution().getEncryptedString("aaa", 1) == "aaa"    # all same characters

# Edge cases
assert Solution().getEncryptedString("a", 100) == "a"      # single character
assert Solution().getEncryptedString("abc", 3) == "abc"    # shift equals length
assert Solution().getEncryptedString("abc", 4) == "bca"    # shift greater than length
assert Solution().getEncryptedString("abcd", 0) == "abcd"  # zero shift
assert Solution().getEncryptedString("xyz", 10000) == "yzx" # large k

Test	Why
"dart", 3	Normal case, cyclic shift within string
"aaa", 1	All identical characters
"a", 100	Single character, large k
"abc", 3	Shift equal to string length, string remains same
"abc", 4	Shift greater than string length, modulo used
"abcd", 0	Zero shift, string unchanged
"xyz", 10000	Large k, checks modulo arithmetic correctness

Edge Cases

One important edge case is when s contains only one character. Any shift should result in the same string because cyclic behavior does not change a single element. Another edge case is when k is a multiple of the string length; this should also result in the same string because the shift effectively wraps around completely. A third edge case is when k is much larger than the string length; naive implementations may attempt repeated shifting, but using modulo ensures efficiency and correctness. All of these edge cases are handled correctly by computing k % len(s) before processing.