Find the string from an array that can be converted to a string S with minimum number of swaps

  

import java.io.*;

import java.util.*;

  

class GFG {

  

    

    

    static String getBestString(String S,

                                List<String> group)

    {

        

        boolean isAnagram = false;

        String bestString = null;

        int minMoves = Integer.MAX_VALUE;

  

        

        int[] charCountS = getCharCount(S);

  

        

        for (String S1 : group) {

  

            

            int[] charCountS1 = getCharCount(S1);

  

            

            boolean anagram

                = checkIsAnagram(charCountS,

                                 charCountS1);

  

            

            if (!anagram)

                continue;

  

            isAnagram = true;

  

            

            

            int moves = findMinMoves(S, S1);

  

            

            if (moves < minMoves) {

                minMoves = moves;

                bestString = S1;

            }

        }

  

        

        return (isAnagram) ? bestString : "-1";

    }

  

    

    

    static int findMinMoves(String S, String S1)

    {

  

        

        int minMoves = 0;

  

        

        int[] fenwickTree = new int[S.length() + 1];

  

        

        

        List<List<Integer> > charPositions

            = getPositions(S1);

  

        

        for (int i = S.length() - 1; i >= 0; i--) {

  

            

            

            List<Integer> temp

                = charPositions.get(

                    S.charAt(i) - 'a');

  

            

            int size = temp.size() - 1;

  

            

            

            int index = temp.remove(size) + 1;

  

            

            

            int leftShift = get(

                fenwickTree, index);

  

            

            update(fenwickTree, index);

  

            

            index -= leftShift;

  

            

            minMoves += Math.abs(i - index + 1);

        }

  

        

        return minMoves;

    }

  

    

    

    static List<List<Integer> > getPositions(

        String S)

    {

        @SuppressWarnings("unchecked")

        List<List<Integer> > charPositions

            = new ArrayList();

  

        for (int i = 0; i < 26; i++)

            charPositions.add(

                new ArrayList<Integer>());

  

        for (int i = 0; i < S.length(); i++)

            charPositions.get(

                             S.charAt(i) - 'a')

                .add(i);

  

        return charPositions;

    }

  

    

    static void update(int[] fenwickTree,

                       int index)

    {

        while (index < fenwickTree.length) {

            fenwickTree[index]++;

            index += (-index) & index;

        }

    }

  

    

    

    static int get(int[] fenwickTree, int index)

    {

        int leftShift = 0;

        leftShift += fenwickTree[index];

  

        while (index > 0) {

            index -= (-index) & index;

            leftShift += fenwickTree[index];

        }

        return leftShift;

    }

  

    

    

    static int[] getCharCount(String S)

    {

        int[] charCount = new int[26];

  

        for (int i = 0; i < S.length(); i++)

            charCount[S.charAt(i) - 'a']++;

  

        return charCount;

    }

  

    

    

    static boolean checkIsAnagram(

        int[] charCountS,

        int[] charCountS1)

    {

  

        for (int i = 0; i < 26; i++) {

            if (charCountS[i] != charCountS1[i])

                return false;

        }

  

        return true;

    }

  

    

    public static void main(String[] args)

    {

  

        

        String S = "abcdac";

  

        

        String arr[] = { "cbdaca",

                         "abcacd",

                         "abcdef" };

  

        String bestString

            = getBestString(S, Arrays.asList(arr));

  

        

        System.out.println(bestString);

    }

}

Let's block ads! (Why?)