Leetcode 3210. Find the Encrypted String
Given a string S
of lowercase alphabet characters, convert it into its “encrypted” form by the following steps:
S
. If the length of S
is odd, the middle character is the middle one. If the length is even, the middle character is the left one of the two “center” characters.The final “encrypted” string is the concatenation of all middle characters found at each step.
To solve this problem, we can use a recursive approach:
public class EncryptedString {
public static String findEncryptedString(String S) {
return encryptHelper(S);
}
private static String encryptHelper(String S) {
if (S.isEmpty()) {
return "";
}
int len = S.length();
int midIndex = (len - 1) / 2; // Middle character index
String middleChar = String.valueOf(S.charAt(midIndex));
String leftPart = S.substring(0, midIndex);
String rightPart = S.substring(midIndex + 1);
// Recursively encrypt the left and right parts
return middleChar + encryptHelper(leftPart) + encryptHelper(rightPart);
}
public static void main(String[] args) {
String S = "abc";
System.out.println(findEncryptedString(S)); // Output: "bac"
}
}
findEncryptedString
method initiates the encryption by calling a helper method encryptHelper
.encryptHelper
method:
The time complexity of this approach is O(n log n):
n
is the length of the input string S
.Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?