```
</td><td>
s = raw_input();
</td></tr>
</table>
## How do I handle ASCII codes?
Also we need to convert between a character and its ASCII code. This is easy in C/C++: a `char` is just a signed 8-bit integer, so we don't need to convert anything. For example, we can enumerate the ASCII codes of all capital letters like this:
for (char c = ‘A’; c <= ‘Z’; c++)
do something
Also if we want the first(or last) digit of the ASCII code of a character(say `'A'`), we just treat it as an integer:
asc = ‘A’;
first_dgt = asc / 10;
last_dgt = asc % 10;
Some other language may have functions converting between ASCII codes and characters. For example, Python provides two functions `ord(char)` and `chr(ascii code)`. You can also google to find out how to do this in your language.
## The solution
Let's consider every character $c$ from `'A'` to `'Z'` separately. Suppose $c$ has ASCII code $\overline{ab}$. Let the input be $s$(a string).
When $a\ne b$, we need to pick both $a$ and $b$ from $s$. We can just check if both digit appears in $s$.
When $a=b$, we need to pick two $a$'s from $s$, thus we need to check if $a$ appears in $s$ twice.
We need to find how many time a character occurs in $s$. This can be done by iterating all chars in $s$. In C you can use `s[i]` to recognize the end of string, since C-style string ends with ASCII 0.(a common mistake is that don't confuse `s[i] != 0` with `s[i] != '0'`. `0` is NULL character but `'0'` has ASCII $48$)
count = 0;
for (int i = 0; s[i] != 0; i++)
if (s[i] == c) count++;
In C++, you can use `string::length()` method to get a string's length:
count = 0;
for (int i = 0; i < s.length(); i++)
if (s[i] == c) count++;
In some languages like Python, things become even easier! Just use `s.count(ch)` to count how many times a char $ch$ appears in a string $s$.
The time complexity is $O(\sigma|s|)$, where $|s|$ is the length of input, and $\sigma=26$ is the size of alphabet.
## A common mistake
If you use C/C++, you may write the following code:
for (int i = 0; i < strlen(s); i++)
do something;
This code may make you TLE. Why? Because `strlen()`'s time complexity is $O(len)$, not $O(1)$. The code above executes $O(|s|)$ `strlen()`'s, and each execution takes $O(|s|)$ time, so the time complexity is actually $O(|s|^2)$.
A small modification should correct this mistake:
int l = strlen(s);
for (int i = 0; i < l; i++)
do something;
However, in C++, if `s` is a `string`(rather than a `char` array), the following code is OK:
for (int i = 0; i < s.length(); i++)
do something;
This is because `length()` method is $O(1)$.
### ALTERNATIVE SOLUTION:
We first preprocess $s$, and maintain a table $occur[0\sim 9]$, where $occur[i]$ is the number of times that digit $i$ appears in $s$.
for (int i = 0; s[i]; i++)
occur[s[i] - ‘0’]++;
Let's then do the algorithm above. Suppose the ASCII code we are checking is $\overline{ab}$.
When $a\ne b$, we check if $occur[a]\ge 1$ and $occur[b]\ge 1$.
When $a=b$, we check if $occur[a]\ge 2$.
The time complexity is $O(|s|)$.
### AUTHOR'S AND TESTER'S SOLUTIONS:
Tester's solution can be found [here][444].
Editorialist's solution can be found [here][555].
[111]: http://www.codechef.com/problems/CHEFPDIG
[222]: http://www.codechef.com/SEPT17/problems/CHEFPDIG
[4444]: http://www.codechef.com/users/berezin
[5555]: http://www.codechef.com/users/jingbo_adm
[6666]: http://www.codechef.com/users/r_64
[444]: http://www.codechef.com/download/Solutions/SEPT17/Tester/CHEFPDIG.cpp
[555]: http://www.codechef.com/download/Solutions/SEPT17/Editorialist/CHEFPDIG.py
|