Ce problème demande de déterminer le nombre minimal d’échanges de caractères nécessaires pour transformer une chaîne s1 en une autre chaîne s2, sous la contrainte que les deux chaînes sont des anagrammes. Chaque échange consiste à permuterexactement deux caractères d’une position.

Méthode de Résolution par Recherche en Largeur (BFS)

La approche BFS explore systématiquement tous les états atteignibles à partir de s1 en effcetuant un échange à la fois. À chaque niveau d’itération, on génère tous les nouveaux états obtenus par un unique échange valide, puis on les ajoute à la file si elles n’ont pas encore été visitées. Le premier temps d’atteinte de s2 correspond au nombre minimal d’échanges requis.

n = len(s1)
queue = deque([(s1, 0)])  # État courant + position de comparaison prochaine
seen = {s1}
steps = 0

while queue:
    size = len(queue)
    for _ in range(size):
        curr, idx = queue.popleft()
        if curr == s2:
            return steps

        # Avancer tant que les caractères coincident
        while idx < n and curr[idx] == s2[idx]:
            idx += 1

        # Essayer tous les échanges utiles à partir de idx
        for j in range(idx + 1, n):
            if curr[j] == s2[idx]:
                s_list = list(curr)
                s_list[idx], s_list[j] = s_list[j], s_list[idx]
                next_str = ''.join(s_list)
                if next_str not in seen:
                    seen.add(next_str)
                    queue.append((next_str, idx + 1))
    steps += 1
return -1

</div>### Méthode Optimisée : DFS avec Pruning Heuristique

Cette méthode exploration en profondeur avec backtracking. Elle effectue une préfiltrage des positions non alignées entre `s1` et `s2` pour réduire l’espace d’états. Deux types de pruning sont appliqués :

- Skipping automatique des positions déjà alignées
- Estimation: `min_swaps_needed ≥ ⌈m / 2⌉`, où `m` est le nombre de caractères restants décalés

<div>```
 int:
    different_s, different_t = [], []
    for a, b in zip(s1, s2):
        if a != b:
            different_s.append(a)
            different_t.append(b)

    m = len(different_s)
    if m == 0:
        return 0

    best = m - 1  # borne supérieure initiale

    def dfs(idx: int, cost: int):
        nonlocal best
        # Ignorer le préfixe déjà aligné
        while idx < m and different_s[idx] == different_t[idx]:
            idx += 1
        if idx == m:
            best = min(best, cost)
            return
        if cost >= best:
            return  # pruning de bound

        # estimation heuristique
        remaining_mismatch = sum(1 for i in range(idx, m) if different_s[i] != different_t[i])
        estimate = (remaining_mismatch + 1) // 2
        if cost + estimate >= best:
            return  # pruning d’heuristique

        # exploration des échanges utiles
        for j in range(idx + 1, m):
            if different_s[j] == different_t[idx]:
                different_s[idx], different_s[j] = different_s[j], different_s[idx]
                dfs(idx + 1, cost + 1)
                different_s[idx], different_s[j] = different_s[j], different_s[idx]

    dfs(0, 0)
    return best

L’heuristique utilisée ici est basée sur le nombre de paires de caractères mal placés divisé par 2 (borne inférieure du nombre d’échanges nécessaires). La file de priorité stocke une structure de type :

[f(n) = g(n) + h(n), chaine_courante, index_début]

Où :

• g(n) : distance réelle du nœud initial
• h(n) : estimation heuristique du reste

On garde trace des coûts minimaux vers chaque nœud pour éviter les réexplorations coûteuses.

def neighbors(node: str, start_idx: int) -> list[str]:
    while start_idx < len(node) and node[start_idx] == s2[start_idx]:
        start_idx += 1
    res = []
    arr = list(node)
    for j in range(start_idx + 1, len(node)):
        if arr[j] == s2[start_idx]:
            arr[start_idx], arr[j] = arr[j], arr[start_idx]
            res.append(''.join(arr))
            arr[start_idx], arr[j] = arr[j], arr[start_idx]
    return res

if s1 == s2:
    return 0

heap = [(heuristic(s1), s1, 0)]
dist = {s1: 0}

while heap:
    f_score, curr, idx = heappop(heap)
    if curr == s2:
        return dist[curr]

    for nxt in neighbors(curr, idx):
        tentative = dist[curr] + 1
        if nxt not in dist or dist[nxt] > tentative:
            dist[nxt] = tentative
            h = heuristic(nxt)
            heappush(heap, (tentative + h, nxt, idx + 1))

return -1

</div>Les trois méthodes permettent de traverser efficacement le graphe d’état, mais leur performance dépend fortement de l’ordre dans lequel les branchse sont explorées. En pratique, l’heuristique A\* ou DFS avec pruning offrent des gains importants sur des chaînes de taille modérée.