Interview Questions/Coding/Distinct Mirror Token Count

Distinct Mirror Token Count

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Distinct Mirror Token Count

A compliance index stores mirrored tokens found in a log. A token is mirrored if it is a substring that reads the same forward and backward. The index stores each distinct mirrored token only once, even if that token appears many times at different positions. Your task is to determine how many unique mirrored tokens exist in the log. Input Format: You are given a string s. Output Format: Return the number of distinct palindromic substrings of s.

Examples

Example 1

Input:

s = "abaaa"

Output:

Explanation: The distinct mirror tokens are ["a", "b", "aa", "aaa", "aba"]. Count = 5, so the output is 5.

Approach hint

Expand every center and add the produced palindrome to a set.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp