Difficult Amazon OA problem

Блог пользователя bokuto_alright

Автор bokuto_alright, история, 2 года назад, По-английски

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

bokuto_alright
2 года назад
6

Комментарии (4)

Показать архивные | Написать комментарий?

why___me

2 года назад, скрыть # |

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

→ Ответить

bokuto_alright

2 года назад, скрыть # ^ |

It is. Thank you

→ Ответить

HarshSingh_24

2 года назад, скрыть # ^ |

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.

→ Ответить

DebNayak05

2 года назад, скрыть # ^ |

← Rev. 3 →

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

My Code

void solve()
{
    string s;
    cin>>s;
    int n = s.size();
    int tot_str = (n*(n-1))/2;
    tot_str++;
    vector<int>hash(26, 0);
    for (auto it : s)
    {
        hash[it-'a']++;
    }
    int to_sub = 0;
    for (auto it : hash)
    {
        to_sub+=((it*(it-1))/2);
    }
    cout<<tot_str-to_sub<<endl;
}

→ Ответить