PalindromesCount
Member Single Round Match 474 · 2009-12-03 · by maksay
Member Single Round Match 474 · 2009-12-03 · by maksay · Brute Force, Simple Search, Iteration
Problem Statement
Problem Statement
A palindrome is a string that is the same whether it is read from left to right or from right to left. Little Dazdraperma likes
palindromes a lot. As a birthday gift she received two strings A and B. Now she is curious if there is a
way to insert string B into string A so that the resulting string is a palindrome. You agreed to help her and
even tell how many different variants of such insertions exist. Two variants are considered different if
string B is inserted in different places. Return the number of possible insertion variants.
For example, let A="aba" and B="b". You can insert B in 4 different places:
For example, let A="aba" and B="b". You can insert B in 4 different places:
- Before the first letter of A. The result is "baba" and it is not a palindrome.
- After the first letter 'a'. The result is "abba" and it is a palindrome.
- After the letter 'b'. The result is "abba" and it is also a palindrome.
- After the second letter 'a'. The result is "abab" and it is not a palindrome.
Constraints
- A and B will each contain between 1 and 50 characters, inclusive.
- Each character of A and B will be a lowercase letter ('a'-'z').
Examples
0)
"aba" "b" Returns: 2
The example from the problem statement.
1)
"aa" "a" Returns: 3
Here every possible insertion point gives you a palindrome.
2)
"aca" "bb" Returns: 0
No possible solutions.
3)
"abba" "abba" Returns: 3
4)
"topcoder" "coder" Returns: 0
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PalindromesCount with a public method int count(string A, string B) · 119 test cases · 2 s / 256 MB per case