Problem Link-https://www.codechef.com/problems/DISTCODE
how to use 2d boolean array?
An easy approach could be to insert all 2 letter sub-strings into a set and then just prining the size of the set (since a set stores distinct elements). If you don’t know about sets, I’d suggest you learn about it, it’s quite useful in CP.
2 Likes
i know about sets in stl,but in this question i have to generate all substrings and check thier length and insert into set?
im also familar with collection frameworks in java,but please explain the approach? what about 2d array of 26*26?
No, all you need to do is insert contiguous sub-strings that are of size 2. you can start a loop from 0 to less than n-1 and then insert sunstring(s,i,i+1). After the loop, print the size of the set.
You can use a Boolean array B of size 26*26, each row and column representing an alphabet from A(0) to Z(25).
Initialize everything to zero.
run a loop from 0 to less than n-1
make B[s[i]-‘A’][s[i+1]-‘A’]=1
Note: A subtracted to convert the value of s[i] to int( 0 for A and 25 for Z)
what is logic behind this 26*26 array?
Each row denotes the first letter of the 2 lettered sub string ad column denotes the second letter. Eg: b[1][1] represents the sub string BB. So, once BB is encountered, you set B[1][1] to 1. If BB is encountered again, you set B[1][1] to 1 again, which has no effect. Hence BB will be counted only once, regardless of how many times it occurred.