Problem Link - Swapping Chefs Way Practice Problem in 1000 to 1400 difficulty problems
Problem Statement:
Given a string S
of length N
, he wants to know whether he can sort the string using his algorithm. According to the algorithm, one can perform the following operation on string S
any number of times:
Choose some index i
(1≤i≤N)
and swap the i-th
character from the front and the i-th
character from the back. More formally, choose an index i
and swap S(i)
and S(N+1−i)
. Help Chef find if it is possible to sort the string using any (possibly zero) number of operations.
Approach:
Steps:
- Make copy of input string (to compare with the sorted version).
- Iterate over the first half of the string and swap characters in pairs of symmetric positions (i.e., for
i
from0
toN/2 - 1
, swapS[i]
andS[N-i-1]
ifS[i] > S[N-i-1]
). - Finally, check if the modified string is equal to the sorted string.
- If yes, print
"YES"
, otherwise print"NO"
.
Complexity:
- Time Complexity: Sorting the string takes
O(N log N)
. The loop for swapping characters runs inO(N/2)
, which is effectivelyO(N)
. Hence, the time complexity for each test case isO(N log N)
, - Space Complexity:
O(N)
as we are storing the input string in another string.