Problème : Étant donné une chaîne de caractères, trouver le caractère qui apparaît le plus consécutivement ainsi que son nombre d'occurrences. Par exemple, dans la chaîne 'aabbcccddeeee112233', le caractère le plus consécutif est 'e' avec 4 occurrences.

Analyse :

• Approche traditionnelle avec boucles imbriquées
• Utiliser des boucles imbriquées pour compter les occurrences consécutives de chaque caractère
• Compelxité temporelle : Bien qu'il s'agissse de boucles imbriquées, la présence de sauts rend la complexité réelle en O(n)
• Méthode des deux pointeurs
• Définir deux pointeurs i et j
• Garder j fixe et déplacer i
• Tant que les caractères aux positions i et j sont identiques, continuer à déplacer i
• Lorsque les caractères diffèrent, enregistrer le résultat et déplacer j pour rattraper i
• Complexité temporelle : O(n)

Implémentation du code :

• Méthode avec boucles imbriquées O(n)

/**
 * @description Trouver le caractère consécutif le plus fréquent et son nombre
 */
interface Resultat {
    caractere: string,
    longueur: number
}

/**
 * Méthode avec boucles imbriquées
 * @param chaine La chaîne à analyser
 * @returns L'objet avec le caractère et sa longueur
 */
export function trouverCaractereConsécutif1(chaine: string): Resultat {
    const resultat: Resultat = {
        caractere: '',
        longueur: 0
    }
    
    const longueur = chaine.length
    if(longueur === 0) {
        return resultat
    }
    
    for(let i = 0; i < longueur; i++) {
        const temp = chaine[i]
        let tempLongueur = 1
        
        for(let j = i + 1; j < longueur; j++) {
            if(temp === chaine[j]) {
                tempLongueur++
            }
            // Cas où les caractères diffèrent ou fin de la chaîne
            if(temp !== chaine[j] || j === longueur - 1) {
                if(tempLongueur > 1 && tempLongueur > resultat.longueur) {
                    resultat.caractere = temp
                    resultat.longueur = tempLongueur
                }
                i = j - 1 // Sauter les caractères déjà traités
                break
            }
        }
    }
    return resultat
}

• Méthode avec deux pointeurs O(n)

/**
 * Méthode avec deux pointeurs
 * @param chaine La chaîne à analyser
 * @returns L'objet avec le caractère et sa longueur
 */
interface Resultat {
    caractere: string,
    longueur: number
}

export function trouverCaractereConsécutif2(chaine: string): Resultat {
    const resultat: Resultat = {
        caractere: '',
        longueur: 0
    }
    
    const longueur = chaine.length
    if(longueur === 0) return resultat
    
    let i = 0
    let j = 0
    let longueurTemp = 0
    
    for(; i < longueur; i++) {
        if(chaine[i] === chaine[j]) {
            longueurTemp++
        }
        
        // Cas où les caractères diffèrent ou fin de la chaîne
        if(chaine[i] !== chaine[j] || i === longueur - 1) {
            if(longueurTemp > 1 && longueurTemp > resultat.longueur) {
                resultat.caractere = chaine[j]
                resultat.longueur = longueurTemp
            }
            
            if(i < longueur - 1) {
                j = i // Déplacer j pour rattraper i
                i-- // Compenser l'incrémentation suivante de i
            }
            longueurTemp = 0
        }
    }
    return resultat
}

Cas de test :

/**
 * Tests pour la fonction de recherche de caractères consécutifs
 */
import {trouverCaractereConsécutif1, trouverCaractereConsécutif2} from './caractere-consécutif'

describe('Tests pour la recherche de caractères consécutifs', () => {
    it('Cas normal', () => {
        const res1 = trouverCaractereConsécutif1('aabbcccddeeee112233')
        const res2 = trouverCaractereConsécutif2('aabbcccddeeee112233')
        expect(res1).toEqual({caractere: 'e', longueur: 4})
        expect(res2).toEqual({caractere: 'e', longueur: 4})
    })
    
    it('Chaîne vide', () => {
        const res1 = trouverCaractereConsécutif1('')
        const res2 = trouverCaractereConsécutif2('')
        expect(res1).toEqual({caractere: '', longueur: 0})
        expect(res2).toEqual({caractere: '', longueur: 0})
    })
    
    it('Pas de caractères consécutifs', () => {
        const res1 = trouverCaractereConsécutif1('abcedrg')
        const res2 = trouverCaractereConsécutif2('abcedrg')
        expect(res1).toEqual({caractere: '', longueur: 0})
        expect(res2).toEqual({caractere: '', longueur: 0})
    })
    
    it('Tous les caractères consécutifs', () => {
        const res1 = trouverCaractereConsécutif1('aaaaaa')
        const res2 = trouverCaractereConsécutif2('aaaaaa')
        expect(res1).toEqual({caractere: 'a', longueur: 6})
        expect(res2).toEqual({caractere: 'a', longueur: 6})
    })
})