How should I practice Total Palindrome Substring Cost?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Uber online assessment problems in FastPrep.

Is Total Palindrome Substring Cost associated with Uber?

FastPrep tags this as a Uber coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem Brief

Total Palindrome Substring Cost

FULLTIMEOA

See Uber online assessment and hiring insights

Given a lowercase string s, consider every substring s[l..r]. Define the cost of a substring as the minimum number of single-character replacements needed to make that substring a palindrome.

A replacement may change any character in the substring to any other lowercase letter. Return the sum of the costs over all substrings of s.

1Example 1

Input

s = "abc"

Output

Explanation

The substrings "ab", "bc", and "abc" each have cost 1. Single-character substrings have cost 0, so the total is 3.

2Example 2

Input

s = "a"

Output

Explanation

A single-character string is already a palindrome.

3Example 3

Input

s = "aabb"

Output

Explanation

The non-zero costs are "ab" = 1, "aab" = 1, "abb" = 1, and "aabb" = 2. The total is 5.

Constraints

Limits and guarantees your solution can rely on.

1 <= s.length <= 2 * 10^5
s contains lowercase English letters.
The return value may exceed the 32-bit integer range.

Draft autosaves locally

public long totalPalindromeSubstringCost(String s) {
  // write your code here
}

Input

"abc"

Output

Company OA Practice