Rearrange A String Geeks For Geeks

 Problem Link:

https://practice.geeksforgeeks.org/problems/rearrange-a-string4100/1

Solution:

class Solution

{

    public String arrangeString(String s)

        {

           PriorityQueue<Character>set=new PriorityQueue<Character>();

            int res=0;

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

               if(Character.isDigit(s.charAt(i))){

                    res=res+Character.getNumericValue(s.charAt(i));  

               }

               else{

                   set.add(s.charAt(i));

               }

           }

           StringBuilder sb=new StringBuilder();

          while(!set.isEmpty()){

               sb.append(set.remove());

           }

           sb.append(res);

           return sb.toString();

           

        }

}

Time Complexity:O(N)[N=length of string][GFG Time:1.0/13.1]

Space Complexity:O(1)

Auxillary Space:O(N)[PriorityQueue of characters present in the string. The worst-case string will consist of all characters, not digits. But on average case Auxillary space will be  <O(N) (Here n is the length of the string)]

Total Test Cases:192

Approach:

1. We will traverse the string and if we found a digit then we will add value in res value.

2. If there are characters then we will add them to the priority queue.

Queustion: Why PriorityQueue not list?

Answer: It is simple as we want the characters to be sorted in lexicographical order. For that reason only we are using a priority queue and by the usage of it, we will get output in lexicographical order.

Question: Then why don't we use to set more precisely treeset, it also does sorting and even in better time than queue?

Answer: Yes set is more efficient than queue but we need to keep track of duplicates also. The set frequency of every element will be limited to 1 whatever the number of times it is present in the string, which will give us the wrong output as our final answer string will be of a small length than desired.

For that reason only we use priority queue instead of set.

3. Since the answer demands characters in sorted order first so for that we will append each character from the queue first till it becomes empty. Later we will append the res value.

4. Return string after converting from stringbuilder.

--------------------------------------------------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"