Count Partial Digit Encodings
Autumn Tournament (2016)
Submission name: code.cpp
Problem summary
Keep individual digits, or replace disjoint adjacent digit pairs by letters: 10 becomes a, 11 becomes b, and so on through 35 becoming z. Only the first n letters are available. Count all distinct resulting strings, including leaving the input unchanged.
Input
n, then the digit string.
Output
The number of encodings.
Constraints
0 ≤ n ≤ 26; digit string length at most 50.
Worked example
Original statement sample.
Input
26 10237
Output
4
Solution analysis
- Let ways[i] count the encodings of the first i digits. There is one encoding of the empty prefix, so ways[0]=1. Every encoding either leaves its final digit alone or replaces its final two digits by one letter.
- Keeping the last digit contributes ways[i−1]. A two-digit number value is available exactly when 10≤value<10+n; in that case add ways[i−2]. These choices use disjoint final blocks, so no encoding is counted twice. Digits and letters are different symbols, making the chosen block boundaries recoverable from the encoded string.
- For 10237 with all letters enabled, prefixes have counts 1,1,2,2,4,4, including the empty prefix. Pair 10 can be replaced or retained, and independently pair 23 can be replaced or retained. Thus 10237, a237, 10n7 and an7 give four encodings.
Why it works
Partition encodings by whether their last token is one unchanged digit or a permitted two-digit letter. Removing that last token gives exactly the corresponding shorter-prefix encoding. The two disjoint cases exhaust the possibilities, proving the recurrence by induction.
Watch out. Do not interpret 01 as a letter. n=0 permits no replacements and gives one encoding. A replacement consumes both digits; overlapping pairs cannot both be chosen.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
int letters;
string digits;
cin>>letters>>digits;
int length=static_cast<int>(digits.size());
vector<long long>ways(length+1,0);
ways[0]=1;
for(int used=1;used<=length;used++){
ways[used]=ways[used-1];
if(used>=2){
int value=10*(digits[used-2]-'0')+digits[used-1]-'0';
// The first available letter represents 10.
if(value>=10&&value<10+letters){
ways[used]+=ways[used-2];
}
}
}
cout<<ways[length]<<'\n';
}