Company: Walmart sparkplug
Difficulty: medium
Kingdom of Strings In the Kingdom of Strings, King Lexicon has issued a challenge. Given a string S of lowercase English characters, your task is to find the number of all possible distinct, nonempty substrings (other than "a") that can be used to partition the string S into segments, where each segment is either the substring or "a". For a substring to qualify: It must appear at least once in S. It must not be equal to "a". Additionally, for a substring to be considered valid, at least one segment in the partition must be the chosen substring. Input Format The first line contains a single string S of lowercase English characters. Output Format Print a single integer representing the number of valid substrings that satisfy the given conditions. Examples Input: baba Output: 4 Explanation: The valid substrings that can partition the string "baba" are: "b": The string "baba" can be split as "b" + "a" + "b" + "a", where each segment is either "b" or "a". "ba": The string "baba" can be spli