Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Minimum adjacent swaps to make strings equal

Правка en1, от swordx, 2022-06-17 10:46:18

Given two strings s1 and s2, the task is to find the minimum number of steps required to convert s1 into s2. The only operation allowed is to swap adjacent elements in the first string. Every swap is counted as a single step.

Examples:


Input: s1 = “abcd”, s2 = “cdab” Output: 4 Swap 2nd and 3rd element, abcd => acbd Swap 1st and 2nd element, acbd => cabd Swap 3rd and 4th element, cabd => cadb Swap 2nd and 3rd element, cadb => cdab Minimum 4 swaps are required. Input: s1 = “abcfdegji”, s2 = “fjiacbdge” Output:17

There is a GFG post present for the same question. The time complexity on the post is O(n^2).

GFG post link: https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/

Question is can it be solved in better time complexity.

Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский swordx 2022-06-17 10:46:18 921 Initial revision (published)