Programando Reorganize String con Python

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

34
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Cursos Empresas Blog Live Conf Eventos Precios

0:0016:04

Programando Reorganize String con Python

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase 31 de 34

Clase 31 / 34

Mi solución escrita en Java es la siguiente

En java no vi algo como defaultdict, al final opte por utilizar un hashMap, y en el queue almance los valores con un map.Entry<k, v>

Adicionalmente, en vez de .join() utilize una clase StringBuilder ya que permite un string ser mutable.

Este es mi codigo.

package org.example.reorganizestring;

import java.util.*;

public class ReorganizePriorityQueue {

    class CustomComparable implements Comparator<Map.Entry<Character, Integer>> {

        @Override
        public int compare(Map.Entry<Character, Integer> t1, Map.Entry<Character, Integer> t2) {
            int diff = t1.getValue().compareTo(t2.getValue());

            if (diff > 0) return -1;
            if (diff == 0) return 0;

            return 1;
        }
    }

    PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>(new CustomComparable());

    private void counterOfLetters (String s) {
        HashMap<Character, Integer> counter = new HashMap<>();

        char[] chars = s.toCharArray();
        for (char c : chars) {
            Integer value = counter.containsKey(c) ? counter.get(c) + 1 : 1;
            counter.put(c, value);

            if (value > (chars.length + 1) / 2) {
                return;
            }
        }

        counter.entrySet().forEach(queue::add);
    }

    public String organize (String s) {
        this.counterOfLetters(s);

        if (queue.isEmpty()) return "";
        if (queue.size() == s.length()) return s;

        StringBuilder reorganizedString = new StringBuilder();
        while (queue.size() > 0) {
            Map.Entry<Character, Integer> character1 = queue.poll();
            reorganizedString.append(character1.getKey());

            if (queue.isEmpty()) {
                continue;
            }

            Map.Entry<Character, Integer> character2 = queue.poll();
            reorganizedString.append(character2.getKey());

            if (character1.getValue() > 1) {
                character1.setValue(character1.getValue() - 1);
                queue.add(character1);
            }

            if (character2.getValue() > 1) {
                character2.setValue(character2.getValue() - 1);
                queue.add(character2);
            }
        }

        return reorganizedString.toString();
    }

}

import org.example.reorganizestring.ReorganizePriorityQueue;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertNotNull;

public class ReorganizePriorityQueueTest {

    private void testShouldReturnAnyString (String param, String expected) {
        ReorganizePriorityQueue x = new ReorganizePriorityQueue();

        String organized = x.organize(param);
        assertNotNull(organized);
        assertEquals(expected, organized);
    }

    @Test
    public void shouldReturnEmptyStringBecauseAllTheCharactersAreTheSame () {
        testShouldReturnAnyString("aaa", "");
    }

    @Test
    public void shouldReturnEmptyStringBecauseIsImpossibleReorganize () {
        testShouldReturnAnyString("aabbaaa", "");
    }

    @Test
    public void shouldReturnTheSameStringBecauseThereIsNotAnythingLetterRepeated () {
        testShouldReturnAnyString("abcdef", "abcdef");
    }

    @Test
    public void shouldReturnStringReorganize () {
        testShouldReturnAnyString("aacab", "acaba");
    }

    @Test
    public void shouldReturnStringReorganizeWithTwoLettersRepeated () {
        testShouldReturnAnyString("aaaabcdeee", "aeaeaedacb");
    }

}