Un challenge …
Au début de la semaine, je recevait un mail de mon potentiel futur chef de labo. Celui-ci proposait un petit challenge pour démontrer un peu la motivation des gens … Après quelques recherches, il s’avère que ça faisait partie de l’édition 2006 du Google Code Jam. Voici l’énoncé du problème:
A palindrome is a string that reads the same forward and backward. A palindrome substring is a contiguous sequence of characters taken from a string that form a palindrome. A palindrome substring of a string is maximal if we can’t extend it to get a bigger palindrome substring. For example, string « acdadc » has 2 maximal palindrome substrings – « a » (the first one) and « cdadc ». All other palindrome substrings (like « dad » or « c ») can be extended to « cdadc », so they are not maximal.
You will be given a string[] str. Concatenate the elements of str to form one long string, and return the number of maximal palindrome substrings contained in that string.
You can use any language you want to solve the problem.
You must provide the code for function:
countMaximalPalindromeSubstrings
Parameters: string[]
Returns: int
Example function signature (might vary from one language to another):
int countMaximalPalindromeSubstrings(string[] str)
Constraints
– str will contain between 1 and 50 elements, inclusive.
– Each element of str will contain between 1 and 50 characters, inclusive.
– Each character of each element of str will be a lowercase letter (‘a’-'z’).Examples
0) {« acdadc »}
Returns: 2
The example from the problem statement.1) {« ababab »}
Returns: 2
The two maximal palindrome substrings here are « ababa » and « babab ».2) {« aaaa », »bbb », »axxx »}
Returns: 3
Remember to use the whole input!3) {« abacabbacaacdbdcacxcbbbbcabababacccbazhhaahh »}
Returns: 14
Au début, j’ai passé par mal d’heures à coder, re-coder et à retourner le problème dans tout les sens sans arriver à une solution totalement fonctionnelle. Je vais voir la personne et lui en parle. Il me dit: « C’est faisable en 45 minutes » … Évidement, ça met la puce à l’oreille: j’étais clairement parti dans le mauvais sens.
J’ai tout effacé, tout recommencé. Au bout de 40 minutes: Houra ! Le script était fonctionnel. Rajoutez 10 minutes pour faire un code documenté proprement et hop, c’est bon.
Pour ceux qui voudraient s’amuser là dessus … Allez y. Pour les autres, je joint ma solution (en PHP). C’est certainement pas la solution la plus efficace, mais elle a l’avantage de marcher 
.
