#### Concepts Used:

Heap

#### Difficulty Level:

Hard

#### Problem Statement :

Given a string

`str`

, find first`K`

non-repeating characters in lexicographical order, if all the characters are repeating then print "Not Exist" without quotes.

**See original problem statement here**

#### Solution Approach :

#### Introduction :

We need to print first

`K`

characters in lexicographical order. We can usemin-heap, each time we extract a character from our heap, we check the occurence of the character, if it is`1`

then we will accept the character otherwise reject it.

#### Method 1 :

We can sort first

`k`

characters of the string using any sorting algorithm, now store the frequency of each character of the string. Now take the first`k`

characters which are not repeated and print them.

#### Method 2 :

We need to geneate a min heap of characters of size

`k`

.

In amin-heap, the root always stores the smaller value as compared to itsleft&rightsubtree, 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

insertfirst`k`

characters from`str`

which are non repeating, in the heap. We can keep track of the frequency of each character in`str`

using frequency array. Once we are done creating heap for first`k`

non repeating characters, we willextractall characters one-by-one and print it,

if all the characters in`str`

are repeating print"Not Exist"without quotes.

extract(): Removes the minimum element fromMin-Heap. Time Complexity of this Operation is O(Logn) as this operation needs to maintain the heap property (by callingheapify()) 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 ofmax-heap), than the node.

#### Algorithms :

**Insert()** :

- Insert the item at the last index, and increment the size by 1.
- Then, check if the inserted item is smaller than its parent,
- If yes, then swap the inserted item with its parent.
- If no, then do nothing.
- Now, go to step
`2`

and repeat untill we reach root (first element).

**Extract()** :

- Store the value of the first node of our heap (
`temp = heap[0]`

).- Replace the root node with the farthest right node (last element).
- Decrease the size by
`1`

.`(heap[0] = heap[size-1])`

- Perform
heapifystarting from the new root.- Return the stored value.(
temp)

**Heapify ()** :

- According to data structures and algorithms, if the heap property holds true then you are done.
- else if
- the replacement node value <= its parent nodes value

then swap them, and repeat step 3.- else
- swap the replacement node with the smallest child node, and

repeat step 3.

#### Example:

#### Solutions:

[TABS_R id=1539]

[forminator_quiz id=”1540″]