Small String

Last Updated on March 30, 2022 by Ria Pathak

Concepts Used

Heap

Difficulty Level

Medium

Problem Statement :

Given a string str and an integer q. We have to generate a string S such that it is lexicographically smallest possible, by perform following operations:

• Take any character from the first q characters of str.
• characters of str and append it to S.
• Remove the chosen character from str.
• Repeat the above steps while there are characters left in str.

See original problem statement here

Solution Approach :

Introduction :

Idea is to create a min-heap of characters of size q. Each time we extract a character from our heap and add it to s, we insert a new character from the string str to the heap until the string str not empty.

Method 1 :

We can sort the first q characters of the string and pick the smallest one and append it to s. Now sort the next q characters append the smallest one to s. Repeat the process untill the string is empty.

Method 2 :

We need to geneate a min heap of characters of size q.

• In a min-heap, the root always stores the smaller value as compared to its left & right subtree, this condition needs to be true for every node. We need to insert each item one by one such that it’s parent is always smaller than the item itself. If the parent is greater, then we need to swap the current item with its parent.
• We will insert first q characters from str to the heap. Now we will extract a character and print it , and insert a new character from str.
• We will stop once we have inserted all the characters from str to the heap.
• Finally, we will extract the characters left in our heap and print.

extract(): Removes the minimum element from Min-Heap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.

heapify(): Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller, or greater (in case of max-heap), than the node.

Below is the algorithm of above approach.

Algorithms :

Insert() :

1. Insert the item at the last index, and increment the size by 1.
2. Then, check if the inserted item is smaller than its parent,
3. If yes, then swap the inserted item with its parent.
4. If no, then do nothing.
5. Now, go to step 2 and repeat untill we reach root (first element).

Extract() :

1. Store the value of the first node of our heap ( temp = heap[0] ).
2. Replace the root node with the farthest right node (last element).
3. Decrease the size by 1. (heap[0] = heap[size-1])
4. Perform heapify starting from the new root.
5. Return the stored value.(temp)

Heapify () :

1. if the heap property holds true then you are done.

2. else if

3. the replacement node value <= its parent nodes value
   then swap them, and repeat step 3.

4. else

5. swap the replacement node with the smallest child node, and
   repeat step 3.

Example:

Solutions:

#include <bits/stdc++.h>
using namespace std;
int parent(int i)
{
     return (i-1)/2;
}
int left(int i)
{
     return (i*2)+1;
}
int right(int i)
{
     return (i*2)+2;
}
void swap(char *a,char *b)
{
     char temp = *a;
     *a = *b;
     *b = temp;
}
void insert(char heap[],int *size, int val)
{
     heap[*size]= val;
     int i = *size;
     (*size)++;
     while(i!=0 && heap[parent(i)]>heap[i])
     {
     swap(&heap[parent(i)],&heap[i]);
     i = parent(i);
     }
}
void heapify(char heap[],int i,int size)
{
     int l = left(i);
     int r = right(i);
     int s = i;
     if(l<size && heap[l]<heap[i])
        s = l;
     if(r<size && heap[r]<heap[s])
        s = r;
     if(s!=i)
     {
     swap(&heap[i],&heap[s]);
     heapify(heap,s,size);
     }
}
char extract(char heap[],int *size)
{
     char root = heap[0];
     heap[0] = heap[*size-1];
     (*size)--;
     heapify(heap,0,*size);
     return root;
}
int main()
{
    int t;
    cin>>t;
  while(t--)
  {
    string s;
    int q, size=0;
    cin>>s;
    cin>>q;
    int n = s.length();
    char *heap = (char *)malloc(sizeof(char)*n);
    int i = 0;

    for(int j=0;j<q;j++)
    {
        insert(heap,&size,s[j]);
        i = j+1;
        if(i==n)
         break;
    }
    while(i<n)
    {
        cout<<extract(heap,&size);
        insert(heap,&size,s[i]);
        i++;
    }
    while(size)
    {
         cout<<extract(heap,&size);
    }
    cout<<endl;
  }
 return 0;
}

import java.util.*;
  import java.io.*;

  public class Main {
    static int size;
    static int count;
    static String s="";
    public static void main(String args[]) throws IOException {

      Scanner sc = new Scanner(System.in);
      int t=sc.nextInt();
      for(int j=0;j<t;j++)
      {
        size=0;
        s="";
        String str=sc.next();
        char heap[]=new char[str.length()+1];
        int len=str.length();
        int k= sc.nextInt();
        for(int i=0;i<k;i++)
        {
          insert(heap,str.charAt(i));
        }

        delete(heap);
        for(int i=k;i<len;i++)
        {
          insert(heap,str.charAt(i));
          delete(heap);
        }
        for(int i=0;i<k-1;i++)
        {
          delete(heap);
        }
        System.out.println(s);
      }
    }
    static void insert(char heap[],char data)
    {
      heap[++size]=data;
      int temp=size;
      while(temp>1&&heap[temp/2]>heap[temp])
      {
        swap(heap,temp,temp/2);
        temp=temp/2;
      }

    }
    static void minheapify(char heap[],int i)
    {
      if(size==0)
      return;
      if(i>size/2&&i<=size)
      return;
      int left=2*i;
      int right=2*i+1;
      if(right<=size)
      {
        if(heap[left]>=heap[i]&&heap[right]>=heap[i])
        return;
      }
      else
      {
        if(heap[left]>=heap[i])
        return;
      }
      int smallest;
      if(left<=size&&heap[left]<heap[i])
      {
        smallest=left;
      }
      else
      smallest=i;
      if(right<=size&&heap[right]<heap[smallest])
      smallest=right;
      if(smallest!=i)
      {
        swap(heap,smallest,i);
      }
      minheapify(heap,smallest);
    }
    static void swap(char heap[],int i,int j)
    {
      char temp=heap[i];
      heap[i]=heap[j];
      heap[j]=temp;
    }
    static void delete(char heap[])
    {
      s=s+ heap[1];
      heap[1]=heap[size];
      size=size-1;
      minheapify(heap,1);
    }
  }

[forminator_quiz id="1668"]
This article tried to discuss the concept of heap. Hope this blog helps you understand and solve the problem. To practice more problems on heap you can check out MYCODE | Competitive Programming.