SWAPCW - Editorial

editorial
, , ,
1

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 from 0 to N/2 - 1, swap S[i] and S[N-i-1] if S[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 in O(N/2), which is effectively O(N). Hence, the time complexity for each test case is O(N log N),
  • Space Complexity: O(N) as we are storing the input string in another string.