I have been working on this problem and struggled like 2 to 3 days to come up with a solution on my own. Coming up with an idea initially or trying to even find a pattern and then trying out to get the brute force first by putting everything together, then applying backtracking and dp to it and then later checking for other ways and finally optimizing it.
All the thoughts that went into it or the time that has been spent on solving and the way it all evolved in the end is what this post is all about. Keeping this as a reference to my future self.
The problem goes the following way:
Given a numbers string, get the number of different ways the alphabet strings could be formed where each number represents an alphabet from A - 1 B - 2 C - 3 …… …. Y - 25 Z - 26
Consider the string - �'
Consider this as an array:
[1, 2, 3, 4, 2, 1, 4, 4]
0, 1, 2, 3 4, 5, 6, 7
We need to find out the number of ways this number string could form different alphabet strings.
For the above number string, it could be formed in the following ways:
ABCDBADD LCDBADD -> L - 12 AWDBADD -> W - 23 ABCDUDD -> U - 21 ABCDBND LCDUDD LCDBND AWDUDD AWDBND
So, there are 9 ways to form the alphabet strings with the given number string.
To group 2 numbers together, the number grouping should be >= 10 and <= 26,
The following are the ideas that revolved and the way it finally came out.
Since I need to group 2 numbers together, need to make sure that the first number <= 2 and second number <= 6.
So, came up with an idea that I could represent the grouping as Ƈ' and all other individual numbers as Ɔ'.
For example, 12342144,
First one, ABCDBADD, as per representation, it is as follows:
00000000
since there is no grouping.
For, LCDBADD, representing it as:
1000000, since 12 is represented with L and is a grouping.
Now, the question is how I need to get all different ways with and without groupings.
I know that I can group numbers together only when current digit <= 2 and next digit <= 6.
So, I came up with a way I could collect grouped and ungrouped indices together.
For example,
1 2 3 4 2 1 4 4
0 1 2 3 4 5 6 7 -> indices
groupedIndices = [0, 1, 4, 5]
ungroupedIndices = [2, 3, 6, 7]
I need to get the places count so that I can fill in the number digits and group them based on number of places.
placesCount = (groupedIndices.count * 2) — (continuousCount)
minplacesCount = placesCount — (continuousCount)
Here in the example, placesCount = (4*2) — (2) = 6 minplacesCount = 6–2 = 4
If placesCount == minplacesCount, then calculate the power value as below and return.
power(base: 2, exponent: placesCount)
For others, it is as follows:
So, will be looping from placesCount to minplacesCount and check number of ways this could be done.
For each placesCount, I need to be calculating the number of ways groupings from 0 to maxOnes fit in these places.
I am just representing ones with my groupings and it starts from 0 to maxOnes that can fit in here.
— — — — — —
It is basically starting from placesCount and it goes till minplacesCount.
For zero groupings, it is going to be 1 way as the places are being filled with all zeros.
(0) -> 1
For 1 grouping, reduce the placesCount to (placesCount-1)
(1) -> placesCount -1 – ungroupedIndices.count
For 2 groupings, reduce the placesCount to placesCount-2
num of ones = 2
placesCount = placesCount -2
remainingPlaces = placesCount -2–2
Going through each place from right, we will be checking how ones and zeros count contribute to the overall sum using ungroupedIndices that were collected in the beginning.
For example, for the following string,
"13241426"
01234567 – indices
groupedIndices = [0,2,4,6]
ungroupedIndices = [1,3, 5,7]
placesCount = 2*(groupedIndices.count) – continuousIndicesCount
placesCount = 8 – 0 = 8
minplacesCount = placesCount – continuousIndicesCount
minplacesCount = 8 – 0 = 8
here, placesCount == minplacesCount
So, we will compute the power of 2 as (2^8) and we will return the result.
Now, consider another string which has continuous indices in groupedIndices.
"12342144"
01234567
groupedIndices = [0,1,4,5]
ungroupedIndices = [2]
placesCount = 2*groupedIndices – continuousIndicesCount
placesCount = 2*4 – 2 = 6
minplacesCount = placesCount – 2 = 4
here, having pascal triangle helps a lot as we can get the ways to form a string using ones and zeros by using placesCount and onesCount.
In our case, since placesCount = 6, building a pascal triangle for 6
where left to right represents ones and top to bottom represents placesCount.
Consider this to be pascal
– 0 1 2 3 4 5 6 -> onesCount
1| 1 1
2| 1 2 1
3| 1 3 3 1
4| 1 4 6 4 1
5| 1 5 10 10 5 1
6| 1 6 15 20 15 6 1
Looping through for loop from placesCount to minplacesCount
totalWays = 0
placesCount = 6
onesCount = 0
pascal[placesCount][onesCount] = pascal[6][0] = 1
totalWays += placesCount[6][0] = 1
placesCount = 5
onesCount = 1
pascal[5][1] = 5
12342144
123214
00001 – possible
00010 – possible
00100 – not possible
01000 – possible
10000 – possible
totalWays = 5 – ungroupedIndices.count = 5 – 1 = 4
placesCount = 4
onesCount = 2
pascal[4][2] = 6
totalWays = 6 – (go through places and for each place, get the number of ways ungroupedIndices can be excluded for each place.
12342144
Considering this to be more like
123214
_ _ _ _
0011 – not possible
0101 – possible
0110 – possible
1001 – possible
1010 – possible
1100 – not possible
totalWays = 6 – 2 = 4
Adding all the total ways,
totalWays = 1+4+4 = 9
Doing this way was needing to go through placesCount and again based on each place, we check how many to discard or remove based on indices in ungroupedIndices array.
Another way I found was to take the ungroupedIndices and then check the contribution of each ungrouped index to the overall deduction sum.
For string,
12342144
01234567 -> indices
Converting to below,
123214
012345 -> indices
placesCount = 6
onesCount = 0
pascal[6][0] = 1
placesCount = 5
onesCount = 1
pascal[5][1] = 5 – (contribution of ungroupedIndices sum)
Contribution of ungrouped indices
[2]
123214
012345
grouping for 2 –> 32
onesCount = 1 – 1 = 0
number of ones on left and right will be considered as Ɔ', so considering only places after 1 and onesCount after deducting current one.
pascal[2][0] = 1
totalWays = 1 – – – – – -> 1
placesCount = 5
onesCount = 1
32 is considered as 1
left are zeros and right are zeros
totalWays = 5 – 1 = 4 – – – – – > 2
placesCount = 4
onesCount = 2
_ _ _ _
pascal[4][2] = 6
ungroupedIndices = [2]
123214
considering 1 for ungrouped index,
1 for index 2 -> 32
onesCount = 2 – 1 = 1
placesCount = 4 – 1 = 3
number of ones that can fit on right of 32 -> 2 places are on the right and 2 places on the left.
onesOnRight = 2/2 = 1
we will go from 1 to 0 and get ones on left and calculate sum
onesOnRight = 1
placesCount = 1
pascal[1][1] = 1
onesCount = 1 – 1 = 0
placesCount on left = 2
Overall contribution,
totalWays = pascal[1][1]
totalWays = 1
onesOnRight = 0
placesCount = 2
pascal[2][0] = 1
onesOnLeft = 1
placesCount on left = 1
From equation 2,
(placesCount on left) * pascal[2][0]
totalWays = 1
Combining totalWays with onesOnRight from 1 to 0
totalWays = 1+1 =2
totalWays = pascal[4][2] – totalWays = 6 – 2 = 4 – – – – – > 3
From equation 1, 2, 3,
sum = 1 + 4 + 4 = 9
The following are time and space complexities:
n -> to get the grouped and ungrouped indices
(n^2) –> for calculating pascal triangle
(nmk) -> places count loop, ungrouped indices array and checking contribution on left and right
Time complexity : O(n+(n^2)+(nmk))
Space Complexity: O(n)
Optimization:
Going from the end of the string, we check the element is not Ɔ' to consider the element and then check if this element and next element satisfy the condition, >= 10 and <= 26.
If yes, then update the current and keep looping until we reach the starting point of the string.
Consider the example from before,
�'
01234567
next = 1
nextNext = 0
next is the next element to see if the current+next form a grouping.
nextNext is the count we got till next of the next element.
Consider index 7, element = 4
current = 0
element != 0 – – > current = next = 1
since index is 7, there is no next, so we update next and nextNext and move in loop.
nextNext = next = 1
next = current = 1
index 6
element = 4
current = 0
4!=0 – – – > current = next = 1
44 is not >= 10 and not <= 26
nextNext = next = 1
next = current = 1
index 5
element = 1
current = 0
1!=0 -> current = next = 1
12 forms a grouping ->
current += nextNext – – > as we will combine pair value with the count we got till next to pair
current = 1+1 =2
nextNext = next = 1
next = current = 2
index 4
element = 2
current = 0
2!=0 – – -> current = next = 2
21 forms a grouping, current = 2+1 =3
nextNext = next = 2
next = current = 3
index 3
element = 4
current = 0
4!=0 – – -> current = next = 3
42 doesn't form a grouping, so, current is not updated
nextNext = next = 3
next = current = 3
index 2
element = 3
current = 0
3!=0 – – – > current = next = 3
34 doesn't form a grouping, so, current is not updated
nextNext = next = 3
next = current = 3
index 1
current = 2
2!=0 – – -> current = next = 3
23 forms a grouping,
current += nextNext = 3+3 =6
current = 6
nextNext = next = 3
next = current = 6
index 0
element = 1
current = 0
1!=0 – – – -> current = next = 6
12 forms a grouping,
current += nextNext
current = 6 + 3 = 9
nextNext = next = 6
next = current = 9
Total ways = 9
Let's see the code for the same:
func getWaysToFormDiffStrings(_ string: String) -> Int {
var charsA = Array(string)
var next = 1
var nextNext = 0
let n = charsA.count
for index in stride(from: n-1, through: 0, by: -1) {
let charA = charsA[index]
var current = 0
// considering the element if not zero
if charA != "0" {
current = next
}
// adding to previous count if a pair exists
if index < n-1,
let num = Int(String(charA)+String(charsA[index+1])),
num >= 10 && num <= 26 {
current += nextNext
}
nextNext = next
next = current
}
return next
}The following is the time and space complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Final thoughts:
I wanted to try out various approaches or atleast come up with a solution, could be brute force and then optimize it. It all came up and formed slowly but I kind of had worked on this problem for 3 days wrapping up with optimization on 3rd day. The optimized solution was way better and elegant. The first 2 ways of getting a solution where the time complexity went till like O(n^2), I could implement it using iterative, recursive, backtracking and adding dp to it. It was an experiment to see how I could solve it recognising the pattern or linking various things and trying to find a solution. For the optimized one, I have taken help from AI to see how it can be done in O(n) time.
Being thorough with Dynamic Programming, I think it takes a lot of practice, needs working with various topics, and diving deeper on how it could be implemented for any problem that we work on.
Dynamic Programming is the basis for learning and implementing Graphs.
Looking forward to diving deeper, and learning more about it.
Divya