### bokuto_alright's blog

By bokuto_alright, history, 3 weeks ago,

Saw this on LC discussion and have no idea how to approach. https://leetcode.com/discuss/interview-question/5365200/Amazon-OA

• +3

 » 3 weeks ago, # | ← Rev. 4 →   0 in case if all characters in the password are distinct. The number of distinct passwords formed by reversing any substring would be represented as all substring of size>=2 ie.. ((n*(n+1)/2) -1) - n +1 where ((n*(n+1)/2) -1) accounts for the substring of atleast one character, n is substring of exactly one character and 1 for the case of no reversal.In general, the formula becomes ((n*(n+1)/2) -1)- P +1 where P is the number of palindromic substrings of size >=1. as reversing it would create the same substring.UPD : It's incorrect.
 » 3 weeks ago, # |   0
•  » » 3 weeks ago, # ^ |   0 It is. Thank you
•  » » » 3 weeks ago, # ^ |   0 It seems logically incorrect to me.For example, the answer for "abca" would be 6 {abca, baca, acba, abac, cbaa, aacb}, but the answer from the mentioned solution would be 5, which is incorrect.
•  » » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 No, it is correct actually. I coded up the solution and the answer for abca is 6 only Code for reference -> My Codevoid solve() { string s; cin>>s; int n = s.size(); int tot_str = (n*(n-1))/2; tot_str++; vectorhash(26, 0); for (auto it : s) { hash[it-'a']++; } int to_sub = 0; for (auto it : hash) { to_sub+=((it*(it-1))/2); } cout<
•  » » » » » 3 weeks ago, # ^ |   0 Sorry for the mistake. I misread last time. It is totally correct."A substring would cause overcounting if its endpoints have the same character, as reversing it would create the same substring as reversing the substring of length 2 less formed by removing the leftmost and rightmost character."This is quite logical and must be correct.