An old phone keypad maps digits to letters as follows: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz.
You are given a string of digits, each between 2 and 9. For each position you choose one letter from that digit's set, producing a letter string of the same length as the digit string. Count how many distinct resulting letter strings have no two ADJACENT positions holding the same letter (that is, result[i] != result[i+1] for every valid i).
Line 1: a string of digits, each character in 2-9.
A single integer: the number of valid letter strings with no two adjacent equal letters.
Example 1
Input
23
Expected
9
Explanation
Digits 2 and 3 map to disjoint letter sets {a,b,c} and {d,e,f}; every one of the 3x3=9 combinations already has different adjacent letters, so all 9 count.
Example 2
Input
22
Expected
6
Explanation
Both positions use digit 2's letters {a,b,c}. The first letter has 3 choices; the second must differ from the first, giving 2 choices, for 3x2=6 valid strings.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →