Résoudre la Question d’Entretien : Trouver la Plus Longue Sous-chaîne Palindromique en Python

# Résoudre la Question d'Entretien : Trouver la Plus Longue Sous-chaîne Palindromique en Python

## Introduction

Dans cet article, nous allons explorer comment résoudre un problème classique souvent rencontré lors des entretiens techniques : trouver la plus longue sous-chaîne palindromique dans une chaîne donnée. Un palindrome est une séquence qui se lit de la même manière en avant et en arrière, comme "radar" ou "anna". Quant à une sous-chaîne, c'est simplement une suite contiguë de caractères dans une chaîne. Ce type de problème est important à maîtriser, car il teste non seulement la compréhension des bases algorithmiques, mais aussi la capacité à optimiser les solutions.

## Comprendre le Problème

Le problème peut être énoncé comme suit : pour une chaîne de caractères donnée, identifiez la sous-chaîne la plus longue qui est un palindrome. Par exemple :

- Entrée : `bananas`
- Sortie : `anana`

Quelques considérations spéciales incluent les cas où la chaîne est vide ou ne contient qu'un seul caractère, car ces cas représentent des palindromes en eux-mêmes.

## Approches pour Résoudre le Problème

Plusieurs méthodes peuvent être employées pour résoudre ce problème, allant de la plus brute-force à l'optimisée, chacune ayant ses propres avantages et inconvénients.

### Approche Naïve

L'approche brute-force consiste à générer toutes les sous-chaînes possibles et à vérifier pour chacune si elle est un palindrome. Cette méthode bien que simple, est inefficace pour les longues chaînes en raison de sa complexité temporelle.

**Implémentation en Python :**

```python
def longest_palindromic_substring_brute_force(s):
    def is_palindrome(substr):
        return substr == substr[::-1]

    max_length = 0
    longest_palindrome = ""

    for i in range(len(s)):
        for j in range(i, len(s)):
            current_substring = s[i:j+1]
            if is_palindrome(current_substring) and len(current_substring) > max_length:
                longest_palindrome = current_substring
                max_length = len(current_substring)

    return longest_palindrome

<span class="gh"># Exemple d'utilisation</span>
print(longest_palindromic_substring_brute_force("bananas"))
</code></pre></div>

<p>La complexité de cette approche est (O(n^3)) en temps et (O(1)) en espace.</p>
<h3>Approche Optimisée: Méthode d'Élongation</h3>
<p>La méthode d'élongation consiste à partir d'un point central et à s'étendre vers l'extérieur tant que le palindrome est valide. Chaque caractère et chaque paire de caractères peut être considéré comme un centre potentiel.</p>
<p><strong>Implémentation en Python :</strong></p>
<div class="codehilite"><pre><span></span><code><span class="k">def</span> <span class="nf">longest_palindromic_substring_center_expand</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
    <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="o"><</span> <span class="mi">2</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">s</span>

    <span class="k">def</span> <span class="nf">expand_around_center</span><span class="p">(</span><span class="n">left</span><span class="p">,</span> <span class="n">right</span><span class="p">):</span>
        <span class="k">while</span> <span class="n">left</span> <span class="o">>=</span> <span class="mi">0</span> <span class="ow">and</span> <span class="n">right</span> <span class="o"><</span> <span class="nb">len</span><span class="p">(</span><span class="n">s</span><span class="p">)</span> <span class="ow">and</span> <span class="n">s</span><span class="p">[</span><span class="n">left</span><span class="p">]</span> <span class="o">==</span> <span class="n">s</span><span class="p">[</span><span class="n">right</span><span class="p">]:</span>
            <span class="n">left</span> <span class="o">-=</span> <span class="mi">1</span>
            <span class="n">right</span> <span class="o">+=</span> <span class="mi">1</span>
        <span class="k">return</span> <span class="n">s</span><span class="p">[</span><span class="n">left</span> <span class="o">+</span> <span class="mi">1</span><span class="p">:</span><span class="n">right</span><span class="p">]</span>

    <span class="n">longest_palindrome</span> <span class="o">=</span> <span class="s2">""</span>

    <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">s</span><span class="p">)):</span>
        <span class="n">palindrome_odd</span> <span class="o">=</span> <span class="n">expand_around_center</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">i</span><span class="p">)</span>
        <span class="n">palindrome_even</span> <span class="o">=</span> <span class="n">expand_around_center</span><span class="p">(</span><span class="n">i</span><span class="p">,</span> <span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>

        <span class="n">longest_temp</span> <span class="o">=</span> <span class="n">palindrome_odd</span> <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">palindrome_odd</span><span class="p">)</span> <span class="o">></span> <span class="nb">len</span><span class="p">(</span><span class="n">palindrome_even</span><span class="p">)</span> <span class="k">else</span> <span class="n">palindrome_even</span>
        <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">longest_temp</span><span class="p">)</span> <span class="o">></span> <span class="nb">len</span><span class="p">(</span><span class="n">longest_palindrome</span><span class="p">):</span>
            <span class="n">longest_palindrome</span> <span class="o">=</span> <span class="n">longest_temp</span>

    <span class="k">return</span> <span class="n">longest_palindrome</span>

<span class="c1"># Exemple d'utilisation</span>
<span class="nb">print</span><span class="p">(</span><span class="n">longest_palindromic_substring_center_expand</span><span class="p">(</span><span class="s2">"bananas"</span><span class="p">))</span>
</code></pre></div>

<p>Cette approche optimise la recherche de palindromes en \O(n^2)\ temps et \O(1)\ espace.</p>
<h3>Utilisation de la Programmation Dynamique</h3>
<p>La programmation dynamique construit une table pour stocker les résultats intermédiaires, optimisant ainsi le calcul.</p>
<p><strong>Implémentation en Python :</strong></p>
<div class="codehilite"><pre><span></span><code><span class="k">def</span> <span class="nf">longest_palindromic_substring_dp</span><span class="p">(</span><span class="n">s</span><span class="p">):</span>
    <span class="n">n</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
    <span class="k">if</span> <span class="n">n</span> <span class="o"><</span> <span class="mi">2</span><span class="p">:</span>
        <span class="k">return</span> <span class="n">s</span>

    <span class="n">table</span> <span class="o">=</span> <span class="p">[[</span><span class="kc">False</span><span class="p">]</span> <span class="o">*</span> <span class="n">n</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="p">)]</span>
    <span class="n">max_length</span> <span class="o">=</span> <span class="mi">1</span>
    <span class="n">start</span> <span class="o">=</span> <span class="mi">0</span>

    <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
        <span class="n">table</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="kc">True</span>

    <span class="k">for</span> <span class="n">length</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="p">):</span>
        <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="n">length</span> <span class="o">+</span> <span class="mi">1</span><span class="p">):</span>
            <span class="n">j</span> <span class="o">=</span> <span class="n">i</span> <span class="o">+</span> <span class="n">length</span> <span class="o">-</span> <span class="mi">1</span>
            <span class="k">if</span> <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">==</span> <span class="n">s</span><span class="p">[</span><span class="n">j</span><span class="p">]:</span>
                <span class="k">if</span> <span class="n">length</span> <span class="o">==</span> <span class="mi">2</span> <span class="ow">or</span> <span class="n">table</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">][</span><span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]:</span>
                    <span class="n">table</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span> <span class="o">=</span> <span class="kc">True</span>
                    <span class="k">if</span> <span class="n">length</span> <span class="o">></span> <span class="n">max_length</span><span class="p">:</span>
                        <span class="n">start</span> <span class="o">=</span> <span class="n">i</span>
                        <span class="n">max_length</span> <span class="o">=</span> <span class="n">length</span>

    <span class="k">return</span> <span class="n">s</span><span class="p">[</span><span class="n">start</span><span class="p">:</span><span class="n">start</span> <span class="o">+</span> <span class="n">max_length</span><span class="p">]</span>

<span class="c1"># Exemple d'utilisation</span>
<span class="nb">print</span><span class="p">(</span><span class="n">longest_palindromic_substring_dp</span><span class="p">(</span><span class="s2">"bananas"</span><span class="p">))</span>
</code></pre></div>

<p>Avec une complexité de \O(n^2)\ en temps et en espace, cette approche utilise une technique qui peut être plus lisible pour certains programmeurs.</p>
<h2>Comparaison des Solutions</h2>
<ul>
<li><strong>Approche Naïve :</strong> Facile à comprendre, mais inefficace pour les longues chaînes.</li>
<li><strong>Méthode d'Élongation :</strong> Un bon compromis entre simplicité et performance.</li>
<li><strong>Programmation Dynamique :</strong> Peut être plus facile à raisonner pour certains, mais utilise plus d'espace.</li>
</ul>
<p>Chaque méthode a son efficacité dans des scénarios différents.</p>
<h2>Conseils pour les Entretiens</h2>
<p>Lors d'un entretien, il est crucial de bien expliquer votre raisonnement :</p>
<ul>
<li>Commencez par la méthode la plus simple, puis discutez comment améliorer l'efficacité.</li>
<li>Préparez-vous à approfondir chaque étape.</li>
<li>Montrez votre capacité à analyser les complexités temporelle et spatiale.</li>
</ul>
<p>Expliquer vos choix et montrer une compréhension profonde des concepts sous-jacents fait bonne impression.</p>
<h2>Conclusion</h2>
<p>Trouver la plus longue sous-chaîne palindromique est un exercice riche pour pratiquer différentes techniques algorithmiques. Réviser et ajuster vos solutions vous aidera à mieux intégrer ces concepts. Explorez également d'autres problèmes d'entretien pour développer votre expertise.</p>
<h2>Ressources Supplémentaires</h2>
<ul>
<li><a href="https://leetcode.com/">LeetCode</a> et <a href="https://www.hackerrank.com/">HackerRank</a> pour pratiquer des problèmes similaires.</li>
<li>Livres recommandés : "Cracking the Coding Interview" par Gayle Laakmann McDowell.</li>
<li>Tutoriels en ligne pour approfondir les techniques de programmation dynamique et d'élongation.</li>
</ul>
<h2>Annexes</h2>
<ul>
<li>Code complet des implémentations présenté dans cet article.</li>
<li>Diagrammes de complexité pour chaque méthode.</li>
<li>Illustrations pour une meilleure visualisation des concepts.</li>
</ul>
<div class="codehilite"><pre><span></span><code><span class="gu">## Code Complet</span>

<span class="gu">### Approche Naïve</span>
```python
# Inclure le code complet de l'approche naïve ici

# Inclure le code complet de l'approche optimisée ici

# Inclure le code complet de l'approche de programmation dynamique ici