A string is called "palindrome-like" if it can be rearranged in any way to become a palindrome. eg : aabb is a palindrome as it can be rearranged like abba. For any string you are allowed to change any number of characters in it to make it "palindrome-like". Let this amount for any string be "cost" Find the total sum of palindrome transformation cost of all the substrings of the given string.

eg:
abca ->
    "a", "b", "c", "a", with cost = 0
    "ab", cost = 1, we can change 'b' to 'a' and it becomes "aa" which is a palindrome.
    "abc", cost = 1, we can change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome.
    "abca", cost = 1, we can change 'b' to 'c' and it becomes "acca" which is a palindrome.
    "bc", cost = 1, we can change 'b' to 'c' and it becomes "cc" which is a palindrome.
    "abc", cost = 1, we can change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome.
    "abca", cost = 1, we can change 'b' to 'c' and it becomes "acca" which is a palindrome.
    "bc", cost = 1, we can change 'b' to 'c' and it becomes "cc" which is a palindrome.
    "bca", cost = 1, we can change 'c' to 'a' and it can be rearranged to "aba" which is a palindrome.
    "ca", cost = 1, we can change 'c' to 'a' and it becomes "aa" which is a palindrome.

constraint: n <= 10**5

both problems here: https://leetcode.com/discuss/interview-question/5497148/snowflake-intern-oa-questions

Can anyone please give hints for the 2nd problem, I have no clue how to approach it. Thank you

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

Everyone I know has stopped Competitive Programming after getting a Job which made me sad. Is there no passion for Competitive Programming? Do people really solve all these problems in hopes of getting a better Job. Do Jobs even require you to be CM or IM for the hiring process? It's weird to me since I always did this for fun

Question here: https://www.codechef.com/practice/course/4-star-difficulty-problems/DIFF1900/problems/SEGDIV?tab=statement

I'm intrigued about this submission over here: https://www.codechef.com/viewsolution/82916450

I have no idea why it works. The poster also just left out the proof part and simply wrote, "It's difficult to prove it". Is there any proof of this or is just conveniently satisfies for the given question's constraints? (n <= 500)