Hello friends my name is tushar and
today I'm going to talk about string
permutation problem.
So you're given an input string 'AABC' so
this is the output we are looking for.
Notice how the output is in the lexo-
-graphically sorted order.
So there are a couple of techniques to
solve this problem and the technique we are
going to discuss today outputs the result
in lexicographically sorted order and it
also handles the case where there are duplicate
characters in the input.The more popular
technique which is based on rotation
doesn't do either of them.
So why there are 12 outputs for 'AABC'.So 'AABC' is
4 characters long,so 4 factorial divided by
since there are 2 duplications of
'A' so 2 factorial so this is 4x3x2
by 2 which
12.If the input look something like 'AABBBC'
in this case the total number of output
would be 6 factorial divided by 2
factorial into 3 factorial because
there are 2 count of 'A' and 3 count of 'B' and this
number would be 60.
So next let's see how we're going to
solve this problem.For a input string
'AABC',first we create count array.So there
are 2 counts of 'A',
1 count of 'B' and 1 count of 'C' and
notice how 'ABC' is sorted.Then we're going to
take a result array which is of same size as
my input array.So in this case 4.So the idea
behind the algorithm is to go from left to
right and look for the first available
character.A character is available when
it's count is greater than 0.Then we
put that character into its
corresponding position in the result
array by looking at the depth of the
recursion.So if we have third level in
the recursion then we're gonna put at the
third position and the result array and
then we're gonna go into the recursion
again after decrementing the count
because we use this character and then
if,when we come back from the recursion
we restore the count back to its
original value and then going to the next,
and then look for the next available
character on the right side of this
particular character and keep repeating
this process.
So next let's do the driver of this
entire logic on this input here.Starting
from left
we're looking for first character whose count
is greater than 0.So that character is 'A'.
So first thing we do is we go to its
corresponding position in the result
array.Here we are at the 0th depth
of the recursion so we go to this 0th
position in the result array and 'A'
there.
So this becomes 'A'.Then we're gonna go
into the recursion from here.
So when we go into the recursion we're
going to decrement this count because we
used one instance of 'A' so this really
becomes now
A,B,C,1,1,1.Also I'm going to note
that I went into the recursion
from this character 'A' so when we come
back from the recursion we can continue
from 'A'.So here again
going from left and looking for a
first character whose count is greater
than 0,so that's again
'A' so first we go into it's corresponding
debth and corresponding position in the
result array as per the depth of the
recursion and add 'A' here.
So 'A' here and then from here we're gonna
go into the recursion again with A,B,
C and this time the count becomes 0
because last time it was 1,1 and 1.
So starting from left,we're again looking
for the first character whose count is
greater than 0 and this time it's 'B'.So
first we go to the 2 and add 'B' here
because this is the second depth
of the recursion and then we're gonna go again
into the recursion from here
So this will be A,B,C and this is 0,0
and 1 because we use one instance of it,
'B'
and now we search for character whose
count is greater than 0 and that 'C'.
So first we go here and add 'C' and then go
again into the recursion so A,B,C and
0,0,0.When the count is 0,0,0 it means
that this array must be full and then we're
gonna just output the contents of this
array.So this outputs A,A,B,C.Then we're
gonna go back into the recursion
So from here we end up here and so last
time we were in recursion,we were at 'C'
so there's nothing to do after 'C' so we
go back again into the recursion to this
point,to the,to the third,to the
second depth and notice how we are
restoring the count back to where we
left and so this,last time we went into
the recursion from this point.
So next we're going to explore
from here we're gonna look for the first
character whose count is greater than 0 and
that's 'C'.
So with 'C',this time we're gonna go again
into the recursion.
So what I'm going to do is I'm going to
first put 'C' into the second position
and go into the recursion so this
becomes A,B,C and this time we use one
instance of 'C' so our count looks
something like this.We did not use 'B'
but we used 'C'.
Then again starting from left we are
looking for first character whose count is
greater than 0.So that's 'B' so we go
into the recursion from 'B' and in here
we add 'B' and this looks something
like A,B,C,0,0,0.As the count is
0,0,0 we just output whatever is in
the result array
so that is 'AACB'.Then we're gonna go
back here so we came,we came to this
point from this 'B' so from here we're
going to look for another character whose
count is greater than 0,so there is not.So we go
back into this point so from here we have
already reached the right end of the
array so there is no further to go to,so
we come to this point here.
So now here we're gonna look for
after 'A',we're gonna look for first character whose
count is greater than 0.So that's 'B',so we come
to this point and from 'B' again
we go into the recursion.So
let's do that and before going to the
recursion I'm going to update the
corresponding position in the
result array to 'B'.So we are in the
depth 1,so in the result array
I add, I set this value to be 'B'.Then for,
after we go into the recursion
the count array starts to look something
like this. For 'B' it's 0, for 'A' it's still 1 and for
'C' it's still 1. Then we are going to again
start from the left side and look for
the first available character whose
count is greater than 0 so that's 'A'.
So we go to this particular position and
set this value to 'A' and then we go into
the recursion from here.
So this looks something like A,B,C and
now 'A' is used,'B' is used and 1.
So again we start a new level of
recursion,so when we start a new level
of recursion we again start looking for
a first available character from the
left side,so that's 'C'.So then we're gonna
add 'C' here and then decrement the
count of 'C' and then go again into the
recursion.
So as soon as the value is 0,0,0 we
output the content of this result array
So my third output is 'ABAC'.Then we go
back into the recursion.
So I went into the recursion from,from
here we have already reached the,we have already
reached the right end of this array so
we go back to here and from here I'm
going to look for the first available
character after 'A'.
So the first available character after 'A'
whose count is greater than 0 is 'C' so we are
going to go and add A,B,C,count of
'A' remains same,this becomes 0 and this
becomes 0 because this time we used
'C'.Also I'm going to go into its
corresponding depth in the result array
and set this value to 'C' and now since
we started a new level of recursion
I'm going to again look for the first
available character from the left and then
this time it's 'A' so I'm going to go
to the corresponding position in the
result array and set this value to 'A'
and here this becomes A,B,C,0,0,0.As soon
as this is 0,0,0
we're just going to ouput the result.So
this is 'ABCA'.
So then we go back to the recursion.
From after 'A',we're going to look for first
character,for first character whose count
is greater than 0,there's none so again
we go back to the recursion so
here we have reached the right
end of the array so we again
go back here and now we will continue
from after 'B'.So after 'B' we're
looking for first character whose count is greater
than 0,so that's 'C'.
So from 'C' we're gonna go into the
recursion.So now 'C' is,so we use 1
count of 'C'
so first we're going to make this guy
'C' because at this level we are using 'C'
and then I'm going to set A,B,C,'A' is 1,'B'
is 1 and 'C' is 0.So again starting
from left we're gonna look for first
character whose count is greater than zero
so that's 'A' so we go to set this guy
to be 'A' and here
A,B,B,C and this is 0,1,0 and now the
first character we encounter is 'B' so this value
becomes B and this value becomes A,B,C,0
0,0. So now all characters,all counts are
0 so we ouput this results,
so this is 'ACAB'.Then we go back here
So here after 'B' there is no
character whose count is greater than zero so then
we go back to this level of recursion
and after 'A' we look for a character
whose count is greater than 0.So that's 'B'.So now we're
going to go into the recursion from 'B'
and this will look something like A,1
because now we're using 'B' so this value
becomes 'B',
B,0 and C,0 and now we are going to
look for available character from the left
again so that will be 'A',so we're going
to add 'A' here and this value becomes A,B,C
0,0,0
So again all this,count is 0 so we're gonna
output this result so 'ACBA'.So
these are the first six permutations of
this 'AABC'.
So from here I go back here and there is
no available character here so we go back
here,after 'B' there is no available
character so we come here.
Here we have reached the right end of this
'ABC' so we come back here and from here
we're going to continue to the next
character which will be 'B'.So let's,next let's
do that.
So I rearranged things a little here
so that it fits in my whiteboard so next
let's do remaining part very quickly.So
we went from 'A' to 'B' so we go to 'B'
we set this guy to be 'B',then decrement
the count of 'B' so this really becomes A,B,
C and 2,0,1 and then we go from 'A' so
first we set this value to 'A' and decrement
the count of 'A' so this really becomes
A,B,C,1,0,1 and then we again,and then
we again look for 'A'.
So this really becomes 'A' and this is A,
B,C,0,0,1 and then finally here it will
become A,B,C,0,0,0 and this value will become 'C' so
we will output this as number 7th position,
'BAAC'.So then we go back into the
recursion
so we come to this point,this has already
reached the end of the array so we come to
this point,so we went into the recursion
from this point so next we're going to
go from here and this will become A,B,C
and 1,0,0 because we're going to go into the
recursion from here,last time we went from
here and we add 'C' here and then this
will become A,B,C,0,0,0 because we're
gonna add 'A' here and output this
8th permutation which will be 'BACA'
and then we go back here.
There is nothing to,nothing,no available
character after this so we come back here
this has already reached the right end so
we come back here and then we're gonna
go into the recursion after for the next
available character which is 'C'.So from
'C' we are going to go back into the
recursion
so leave the count of 'A' as,so first we
add 'C' here and leave the count of 'B' as
is B,C
so 2,0,0,look for the first available
character on the left so that's 'A' so
make this 'A' and go into the recursion
again
So A,B,C,so this value is 1,0,0 and then
look again from the left and that value
again will be 'A'.So the next available,so
with this guy becomes 'A' and this value becomes
A,B,C,0,0,0
So at this point,we output this which is
our 9th permutation 'BCAA'.
and then we,we went into the
recursion from here,there is nothing
more available characters here so we come
back here and after 'A' there is no more
available characters so we come back here
after 'C' there are no characters so we go
back to the top and now we go from 'B' to
'C' and repeat the same process.So this
guy becomes 'C' and we go into the
recursion from here
so A,B,C and this is
2,1,0 because we use 1 instance of 'C' and
again we look for first available
character so there will be 'A' so we
go into the recursion from 'A',so this
will become,this will become A,B,C
and this is 1,1,0 and now we have,again look
for the first available character from
here so that again will be 'A' from the
left so again it will be A,B,C,0,1,0 so
this value is again 'A' and then we go
back here and look for the first
available character
so that's 'B' so this becomes 'B' and this
is A,B,C,0,0,0 so we output this as our
10th output 'CAAB' and then we go back into
the recursion,
so this has no more available characters from
here,so this has,here 'B' is available so
we can go again into the recursion with A,
B,C,now the count of 'B will be 0 and
corresponding position,
it will be 'B',so 1,so this will be 0
and this is still available
because now we've entered into the
recursion from 'B' and this will again
set this guy to be 'A' because 'A' is
unused so A,B,C,0,0,0 which means we
need to output this,'CABA' and now we have
one more permutation left so we go back
here there is available character
here so we come back here,there are no
available characters here so we come back
here.
There is,so last time we went into the
recursion from 'A' so going next we have 'B'
left because 'B' has count greater than 1,
greater than 0,so we go into the
recursion at 'B' so A,B,C and 2,0,1 and
this we set to 'B' and 2,0,0 and
this we set to 'B' and from here we go
again into the recursion
with a count,by decrementing count of
'A' so A,B,C and 1,0,0 and then A,B,C,0,0,0
and this is value also becomes 'A' and
this will be our final addition 'CBAA'
and then we go back here to here,there
is no more available character from here so
we go back here there are no more
available characters after 'A' so we've
come back to,go to this point of
recursion
there are no more available characters after C so
we come to this highest top level
of recursion and after 'C' there are no more
characters.So these are our,this are our
all our permutations for this
string 'AABC'.Again you can notice that
they are all in the sorted order.First we take
care of all A's,then B's and then
C's.So the time complexity for this
algorithm is obviously factorial time
because we can have total factorial
permutations and the space complexity
if you're not storing the ouput will be
same as the total number of characters
in the input string because we are at
max going 4 level deep into the
recursion which is the total depth of the
input.So next let's look at the code for
this algorithm.Here is permute,it takes in an
input character array,the characters in
this array might not be sorted and they
could all,there could also be
repetitions.
So first we're going to take a map of
character to integer which is going to
keep the count of every character and
then we're going to store those
characters into the string array and
the count in this count array in a sorted
format.So if we had string ABC we would,our
character array would,our string,this
character string array would have A,B and
C and the count will be 1,1 and 1 and
then we're gonna initialize this result
to store all the intermediate results
and then we call this permuteUtil
which will take this string array 'ABC'
count 1,1,1,result array which is of the
same length as the original input array
and then the level which is the depth of
the recursion.So initially the level
will be 0 and then we keep doing this
recursive stuff.So if level is same as
result.length it's not,so we have i
starting from zero going to the string .
length.So our i could be 0,1 or 2.
Initially i is 0,if count of i is 0 so
count of i which is this value,it's
not zero so we don't go into this if
condition and first thing we do is we
add this into the,we update the result
array with 'A' and then we decrement the count
and then we go into the recursion
So what happens is from here we go into
the recursion and as you can see we have
decremented the count of 'A' to 0 because we
used 'A' and then we're going to look for
the first available character so if,if,
if the count is 0 then we continue and
so basically i comes to i,1.i,0 is kept
because count if i,0,so we come to i,1 and
then we're going to put 'B' into the
result
and then go into the recursion again
from the permuteUtil.
So we go into the third level of
recursion and look for the first
available character so for i,0 and i,1
we'll continue because count of 'A' and
'B' is both 0 so we reach 'C' and then we're
gonna put C into this result at the
third,at the second level,at the second
position because we are at the second
depth level and then we're gonna go
again into the recursion and this time
our level will be same as result.
length
so we're going to just print this array.
So we're going to print 'ABC',all the
contents of this array and then we're
going to just return.
So when we return we go back from here
to this point and here our i is already
reached
2 so there is nothing more for i to go
to so we go back to this level and in
here our i will,i will move on to the
next value of,i will move on to the next
value which is 2.
So this is what happened,these two
recursions are done so they're orange now
while this is now current and our i
becomes 2.
So when i becomes 2, so now we're
going to look at,
so 'A' is already there in the result array
and now we're going to look,we're
going to put 'C' into the result array,so 'C'
goes into the result array and then we
again calle permuteUtil and go into the
recursion again.
So this time we again look for the first
available character and the only available
character this time is 1.
So for count,for i,0 it continues and
we hit for count 1,for count 1 this
value is not 0 so we put this 'B' into
the final result and then call
recursion again and this time and this
time again,the level becomes,level
becomes equal to the result.length so we
print 'A',contents of the result array,'ACB'
and now we're going to go back into
the recursion so as you can notice while
going back into the recursion we are
incrementing the count which we
discriminated before going to the
recursion.
So,we go back here,we,when you
come to this level B we have already
reached,we're already at B and C is
not useful because the count of c is 0 so we
come back to this level and in here i
has already reached
2 so there is nothing much to do at so
we come back to the top level so we'll
come to the place,
we'll come to the lowest level
of the recursion and increment our i to 1.
So when we increment our i to 1 so this is
the 0th level of the recursion so we're
going to,we're going to fill the 0th
level,0th index in the array so this
guy value becomes whatever is this at
this position which is 'B' and then we're
going to decrement the count of B and
then go again into the recursion and we
look for the first available character 'A'
and again the same,same process
happens and we put 'A' into this final
result and then again going to the
recursion and look for the first
available character and that is C and
then we again go into the recursion and
put 'C' into the result array and then
at this point of time our length will
again become too big,
equal to result array,result.length and
we'll just print the contents of this
array 'BAC' and then from here we go back
to here and this is already done all the
eyes have been covered so we come back
to here and we look for the next
available character after this which is C,
1 so that's where we reach.
So here we are going to put 'C' into our
result array because this is the first
level of recursion and then go back into
the recursion and this time the first
available character will be 'A' so we
put that into the result and then we
print 'B','BCA' and then we go back to
the top and this time i will become 2
and so first thing we put is 'C' and then
go into the recursion again and then we
put 'A' and then going to the recursion
again and then we put 'B' and then going
to the recursion again and this is all
done so 'CAB' gets printed and then
we're all back into the recursion so
from here to here and this is all done
so we come to this point and we'll,next
question will start from 'B' so we put
'B' into the final result and then our
next recursion will start from
'A' so 'A' will go into the final result and
then this gets printed and at this point
of time we have printed all the
permutations of this string so we're
pretty much done with the entire
recursion.
So I hope this helps you understand how
this code is working.
So this is all have to talk about string
permutation.The link to this code is in
the description section of the video.
Also i have the code in python for all
the viewers who like python.
Please share this video,comment on this
video,check out my facebook page and
check out my github link.Thanks again
for watching this video.
