Comment trouver le nombre minimum d'opération (s) pour équilibrer la corde?

Je ne pense pas que vous ayez vraiment besoin d'une programmation dynamique ici.

Une approche en O (durée ( S )) temps:

• Itérer sur S , construire une carte de fréquence (une correspondance entre des lettres distinctes A – Z et des nombres). Pour votre exemple ABCB , ce serait A-> 1 B-> 2 C-> 1 D-> 0 E-> 0 ... Z-> 0 , que nous pouvons représenter par le tableau [1, 2, 1, 0, 0, ..., 0] .
  • Nous pouvons le faire parce que nous ne nous soucions pas du tout de la position des lettres; il n'y a pas de réelle différence entre ABCB et ABBC , en ce que chacun peut être équilibré en remplaçant son C par un A .
• Triez le tableau. Pour votre exemple, cela donne [0, 0, ..., 0, 1, 1, 2] .
  • Nous pouvons le faire parce que nous ne nous soucions pas vraiment de quelle lettre était laquelle; il n'y a pas de réelle différence entre ABCB et ABDB , en ce sens que chacun peut être équilibré en remplaçant l'une de ses lettres singleton par l'autre.
• En supposant que la chaîne n'est pas vide (car si elle est vide, la réponse est juste 0), la chaîne équilibrée finale contiendra au moins 1 et au plus 26 lettres distinctes. Pour chaque entier i compris entre 1 et 26, déterminez le nombre d’opérations à effectuer pour produire une chaîne équilibrée avec i lettres distinctes:
  • Tout d'abord, vérifiez que la longueur ( S ) est un multiple de i ; sinon, ce n'est pas possible, alors passez à l'entier suivant.
  • Ensuite, calculez ^{length ( S )} / _i , le nombre de chaque lettre distincte dans la chaîne équilibrée finale.
  • Pour compter le nombre d'opérations à effectuer, nous allons examiner tous les décomptes qui doivent être augmentés . (Nous pourrions, de manière équivalente, examiner les décomptes qui doivent être diminués : ils devront correspondre.)
  • Nous ne sommes intéressés que par les derniers éléments i du tableau trié. Tous les éléments avant ce point représentent des lettres qui n'apparaîtront pas dans la chaîne équilibrée: soit les nombres sont déjà nuls et le resteront, soit ils sont différents de zéro mais seront réduits à zéro. Dans tous les cas, puisque nous ne suivons que les augmentations , nous pouvons les ignorer.
  • Pour chacun des derniers comptages i inférieurs à ^{length ( S )} / _i , ajoutez la différence. Cette somme correspond au nombre d'opérations. (Notez que, puisque les décomptes sont triés, vous pouvez quitter cette boucle interne dès que vous atteignez un décompte supérieur ou égal au décompte cible.)
  • Vous pouvez quitter cette boucle après le premier i qui est supérieur ou égal au nombre de lettres distinctes dans le S d'origine (à part les valeurs de i que nous avons dû ignorer car ils ne divisent pas uniformément la longueur ( S )). Par exemple, si length ( S ) = 100, et que le S original a 19 lettres distinctes, alors nous devons seulement considérer i comme élevé comme 20. (Hat-tip à Eric Wang pour avoir suggéré quelque chose dans ce sens.)
• Renvoyez la plus petite de ces 26 sommes. (Notez que vous n'avez pas réellement besoin de stocker toutes les sommes; vous pouvez simplement garder une trace du minimum.)

Le code suivant implémente la solution, en Java, avec un test unitaire.

L'algorithme est presque identique à la réponse de @ ruakh, sinon identique.

Code

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * BalanceString test.
 *
 * @author eric
 * @date 2/2/19 9:36 PM
 */
public class BalanceStringTest {
    private BalanceString bs = BalanceString.EN_UPPER_INSTANCE;

    @Test
    public void test() {
        // n < m case,
        Assert.assertEquals(bs.balanceCount("AAAABBBC"), 1); // e.g 1A -> B,
        Assert.assertEquals(bs.balanceCount("AAAAABBC"), 2); // e.g 1A -> B, 1C -> B,
        Assert.assertEquals(bs.balanceCount("AAAAAABC"), 2); // e.g 1B -> A, 1C -> A,
        Assert.assertEquals(bs.balanceCount("AAAAAAAB"), 1); // e.g 1B -> A,

        // n > m case,
        Assert.assertEquals(bs.balanceCount("AAAABBBBCCCCDDDDEEEEAAAA"), 4); // add 1 new char, e.g change 4 A to 4 F,
        Assert.assertEquals(bs.balanceCount(genIncSeq(10)), 15); // A-J, 10 distinct chars, 55 in length; solved by add 1 new char, need 15 steps,

        // n == m case,
        Assert.assertEquals(bs.balanceCount(genIncSeq(3)), 1); // A-C, 3 distinct chars, 6 in length; symmetric, solved with same distinct chars, need 1 steps,
        Assert.assertEquals(bs.balanceCount(genIncSeq(11)), 15); // A-K, 11 distinct chars, 66 in length; symmetric, solved with same distinct chars, need 15 steps,

        // n < m, or n > m case,
        Assert.assertEquals(bs.balanceCount("ABAC"), 1); // e.g 1A -> B, or 1A -> D,
    }

    // corner case,
    @Test
    public void testCorner() {
        // m <= 2,
        Assert.assertEquals(bs.balanceCount(""), 0);
        Assert.assertEquals(bs.balanceCount("A"), 0);
        Assert.assertEquals(bs.balanceCount("AB"), 0);
        Assert.assertEquals(bs.balanceCount("AA"), 0);

        /*------ m == n == distinctChars ------*/
        String mndBalanced = genMndBalancedSeq(); // each possible char occurs exactly once, already balanced,
        Assert.assertEquals(mndBalanced.length(), bs.getDistinctChars());
        Assert.assertEquals(bs.balanceCount(mndBalanced), 0); // no need change,

        char lastChar = mndBalanced.charAt(mndBalanced.length() - 1);
        String mndOneDup = mndBalanced.replace(lastChar, (char) (lastChar - 1)); // (distinctChars -2) chars occur exactly once, one occurs twice, one is missing, thus it's one step away to balance,
        Assert.assertEquals(mndOneDup.length(), bs.getDistinctChars());
        Assert.assertEquals(bs.balanceCount(mndOneDup), 1); // just replace the duplicate char with missing char,
    }

    // invalid input,
    @Test(expectedExceptions = IllegalArgumentException.class)
    public void testInvalidInput() {
        Assert.assertEquals(bs.balanceCount("ABAc"), 1);
    }

    // invalid char range, for constructor,
    @Test(expectedExceptions = IllegalArgumentException.class)
    public void testInvalidRange() {
        new BalanceString('z', 'a');
    }

    /**
     * Generate a string, with first char occur once, second twice, third three times, and so on.
     * <p>e.g A, ABB, ABBCCC, ABBCCCDDDD,
     *
     * @param m distinct char count,
     * @return
     */
    private String genIncSeq(int m) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <= i; j++) sb.append((char) (bs.getMinChar() + i));
        }
        return sb.toString();
    }

    /**
     * Generate a string that contains each possible char exactly once.
     * <p>For [A-Z], it could be: "ABCDEFGHIJKLMNOPQRSTUVWXYZ".
     *
     * @return
     */
    private String genMndBalancedSeq() {
        StringBuilder sb = new StringBuilder();
        char minChar = bs.getMinChar();
        int distinctChars = bs.getDistinctChars();

        for (int i = 0; i < distinctChars; i++) {
            sb.append((char) (minChar + i));
        }
        return sb.toString();
    }
}

BalanceStringTest.java
(Test unitaire, via TestNG)

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * Assume string only contains A-Z, the 26 uppercase letter,
 * <p>given a string, you can replace a char with another char from the 26 letter,
 * <p>figure out the minimum replacement required to make the string balance,
 * <p>which means each char in the string occurs the same time,
 *
 * @author eric
 * @date 2/2/19 8:54 PM
 */
public class BalanceString {
    private final char minChar;
    private final char maxChar;
    private final int distinctChars; // total distinct char count,

    public static final BalanceString EN_UPPER_INSTANCE = new BalanceString('A', 'Z');

    public BalanceString(char minChar, char maxChar) {
        this.minChar = minChar;
        this.maxChar = maxChar;
        this.distinctChars = maxChar - minChar + 1;

        if (distinctChars <= 0)
            throw new IllegalArgumentException("invalid range of chars: [" + minChar + ", " + maxChar + "]");
    }

    /**
     * Check minimal moves needed to make string balanced.
     *
     * @param str
     * @return count of moves
     */
    public int balanceCount(String str) {
        // System.out.printf("string to balance:\t%s\n", str);
        int len = str.length(); // get length,
        if (len <= 2) return 0; // corner cases,

        Map<Character, Integer> coMap = figureOccurs(str); // figure occurrences,
        Integer[] occurs = sortOccursReversely(coMap); // reversely order occurrences,

        int m = coMap.size(); // distinct char count,
        int maxN = (len < distinctChars ? len : distinctChars); // get max possible distinct char count, included,

        int smallestMoves = Integer.MAX_VALUE; // smallest moves, among all possible n,

        // check each possible n, and get its moves,
        for (int n = 1; n <= maxN; n++) {
            if (len % n == 0) {
                int moves = figureMoves(len, coMap, occurs, m, n);
                if (moves < smallestMoves) smallestMoves = moves;
            }
        }

        return smallestMoves;
    }

    /**
     * Figure occurs for each char.
     *
     * @param str
     * @return
     */
    protected Map<Character, Integer> figureOccurs(String str) {
        Map<Character, Integer> coMap = new HashMap<>();
        for (char c : str.toCharArray()) {
            if (c < minChar || c > maxChar)
                throw new IllegalArgumentException(c + " is not within range 'A-Z'");

            if (!coMap.containsKey(c)) coMap.put(c, 1);
            else coMap.put(c, coMap.get(c) + 1);
        }

        return coMap;
    }

    /**
     * Get reverse sorted occurrences.
     *
     * @param coMap
     * @return
     */
    protected Integer[] sortOccursReversely(Map<Character, Integer> coMap) {
        Integer[] occurs = new Integer[coMap.size()];

        coMap.values().toArray(occurs);
        Arrays.sort(occurs, Collections.reverseOrder());

        return occurs;
    }

    /**
     * Figure moves needed to balance.
     *
     * @param len   length of string,
     * @param coMap
     * @param m     original distinct elements count,
     * @param n     new distinct elements count,
     * @return count of moves,
     */
    protected int figureMoves(int len, Map<Character, Integer> coMap, Integer[] occurs, int m, int n) {
        int avgOccur = len / n; // average occurrence,
        int moves = 0;

        if (n == m) { // distinct chars don't change,
            for (Integer occur : occurs) {
                if (occur <= avgOccur) break;
                moves += (occur - avgOccur);
            }
        } else if (n < m) { // distinct chars decrease,
            for (int i = 0; i < n; i++) moves += Math.abs(occurs[i] - avgOccur); // for elements kept,
            for (int i = n; i < m; i++) moves += occurs[i]; // for elements to replace,
            moves >>= 1;
        } else { // distinct chars increase,
            for (int i = 0; i < occurs.length; i++) moves += Math.abs(occurs[i] - avgOccur); // for existing elements,
            moves += ((n - m) * avgOccur); // for new elements,
            moves >>= 1;
        }

        return moves;
    }

    public char getMinChar() {
        return minChar;
    }

    public char getMaxChar() {
        return maxChar;
    }

    public int getDistinctChars() {
        return distinctChars;
    }
}

Tous les cas de test réussiraient.

Complexité

• Heure: O (len) + O (m * lg (m)) + O (m * factorCount)
  • Chaque scan séquentiel prend O (len) , il y a plusieurs boucles séquentielles.
  • Le tri du tableau prend O (m * lg (m)) , qui est au plus O (distinctChars * lg (distinctChars)) , donc constant, et seulement trier une fois.
  • Pour déterminer les mouvements pour chaque n, prend O (m) .
  • Le nombre de n nécessaires pour représenter les mouvements dépend du nombre de nombres divisibles pour len, dans la plage [ minChar , maxChar ].
    Ce nombre est petit et constant aussi.
• Espace: O (len)
  • La chaîne d'entrée nécessite O (len) .
  • Le hashmap du compteur nécessite O (m) .
  • Le tableau d'occurrences triées nécessite O (m) .

Où :

• len est la longueur de la chaîne.
• m est un nombre de caractères distinct dans la chaîne d'origine
• distinctChars est un nombre de caractères distinct, par exemple 26.
• maxN nombre maximum de caractères distincts possibles, inclus,
• factorCount nombre de nombres divisibles dans la plage [1, n] , par len ,
• minChar caractère min, par exemple A
• maxChar max char, par exemple Z

Et:

• len > = m
• m distinctChars