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

Before contest

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

3 days

Register now »

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

3 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 155 |

5 | -is-this-fft- | 150 |

6 | Petr | 148 |

6 | SecondThread | 148 |

8 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2024 02:48:47 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

Same problem as this? https://stackoverflow.com/questions/78108438/number-of-unique-strings-that-can-be-formed-by-reversing-one-substring-of-a-stri

It is. Thank you

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.

No, it is correct actually. I coded up the solution and the answer for abca is 6 only Code for reference ->

My CodeSorry 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.