Katkat
Back

Reorder a String by Alternating Its Left and Right Ends

Capital OneSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests string manipulation, two-pointer logic, and the ability to efficiently manage index traversal in both directions simultaneously.

Problem Statement

Given a string s, generate a new string by alternately picking characters from the front and the back of s until all characters have been used. Specifically, you should pick the first available character from the left, then the first available character from the right, then the second from the left, then the second from the right, and so on.

Function Signature

def reorder_alternating(s: str) -> str:

Constraints

  • s length is between 0 and 10^5.
  • The string can contain any Unicode characters, including spaces and symbols.
  • The algorithm should run in O(n) time complexity.

Examples

Example 1: Input: s = "abcde" Output: "aebdc" Explanation: Pick 'a' (index 0), then 'e' (index 4), then 'b' (index 1), then 'd' (index 3), then 'c' (index 2).

Example 2: Input: s = "1234" Output: "1423" Explanation: Pick '1', then '4', then '2', then '3'.

Edge Cases

  • Empty string: should return an empty string.
  • Single character string: should return the same character.
  • Strings with spaces: spaces must be preserved exactly as they appear in the original string.

Hints

Hint 1

Use two pointers, one starting at the beginning of the string (index 0) and one at the end (index len(s) - 1).

Hint 2

Use a loop that continues until the left pointer is greater than the right pointer.

Hint 3

Be careful with the termination condition to ensure you do not add the same character twice when the string has an odd number of characters.

Follow-up questions

  • How would you modify your solution to perform the operation in-place if the input were an array of characters instead of a string?
  • What is the space complexity of your current approach, and can you optimize it if you are limited by memory?
  • How would the logic change if you were asked to pick two characters from the left and one from the right in every cycle?