algoadvance

Leetcode 3210. Find the Encrypted String

Problem Statement

Given a string S of lowercase alphabet characters, convert it into its “encrypted” form by the following steps:

  1. Find the middle character of 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.
  2. Append that character to the answer, then split the string into two halves (excluding the middle character) and repeat until no characters are left.

The final “encrypted” string is the concatenation of all middle characters found at each step.

Clarifying Questions

Strategy

To solve this problem, we can use a recursive approach:

  1. Define a helper function that takes a string and returns its “encrypted” form.
  2. Find the middle character of the string and add it to the result.
  3. Recursively process the left and right substrings (excluding the middle character) until the string is empty.
  4. Concatenate and return the resulting middle characters.

Code

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"
    }
}

Explanation:

  1. The findEncryptedString method initiates the encryption by calling a helper method encryptHelper.
  2. The encryptHelper method:
    • Base case: If the string is empty, return an empty string.
    • Calculate the middle character’s index.
    • Extract the middle character.
    • Form the left and right substrings.
    • Concatenate the middle character with recursively computed encrypted versions of the left and right substrings.

Time Complexity

The time complexity of this approach is O(n log n):

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI