Programando Reorganize String con Python

La solución de la profe solo me ejecutó si cambiaba las líneas 8 y 9 por:

    for caracter  in ocurrenciasPorCaracter:
        colaPrioridad.append((-ocurrenciasPorCaracter[caracter], caracter))

**Lo ejecuté en línea en:
**

Código completo:

import heapq
from collections import defaultdict


def reorganizeString(S: str) -> str:
    ocurrenciasPorCaracter = defaultdict(int)
    for caracter in S:
        ocurrenciasPorCaracter[caracter] += 1
        if ocurrenciasPorCaracter[caracter] > (len(S)+1) / 2: return ""
    colaPrioridad = []
    for caracter  in ocurrenciasPorCaracter:
        colaPrioridad.append((-ocurrenciasPorCaracter[caracter], caracter))
    heapq.heapify(colaPrioridad)

    stringOrdenada = []
    while 2 <= len(colaPrioridad):
        ocurrencia1, caracter1 = heapq.heappop(colaPrioridad)
        ocurrencia2, caracter2 = heapq.heappop(colaPrioridad)
        stringOrdenada.append(caracter1)
        stringOrdenada.append(caracter2)
        if ocurrencia1 + 1: heapq.heappush(colaPrioridad, (ocurrencia1 +1, caracter1))
        if ocurrencia2 + 1: heapq.heappush(colaPrioridad, (ocurrencia2 +1, caracter2))

    if colaPrioridad: return "".join(stringOrdenada) + colaPrioridad[0][1]
    return "".join(stringOrdenada)
    
    
print(reorganizeString("aaaii"))    

Este recurso me ayudó mucho <https://stackfull.dev/heaps-in-javascript> porque no lograba entener **por qué la** **heap es tan importante** y es básicamente un binary tree, entonces hay formas de insertar un nodo de forma que el árbol sigue ordenado sin necesidad de usar un sorting algorithm para re organizar la lista. Entonces cuál es el punto? **Sorting algorithms** no son tan rápidos. La heap nos ayuda a evitarlos básicamente. Creo que esa es la forma más simple de explicarlo pero por favor comenten si hace falta algo.

Comparto una solución distinta: `import heapq` `class Solution:` ` def reorganizeString(self, s: str) -> str:` ` frequency_characters = {}` ` s_len_half = (len(s) + 1) // 2` ` for char in s:` ` frequency_characters[char] = frequency_characters.get(char, 0) + 1` ` if frequency_characters[char] > s_len_half:` ` return ""` ` max_heap = []` ` for char, freq in frequency_characters.items():` ` heapq.heappush(max_heap, (-freq, char))` ` result = []` ` prev_char = None` ` prev_freq = 0` ` while max_heap:` ` freq, char = heapq.heappop(max_heap)` ` result.append(char)` ` if prev_freq < 0:` ` heapq.heappush(max_heap, (prev_freq, prev_char))` ` prev_char = char` ` prev_freq = freq + 1` ` return "".join(result)`

```python import heapq from collections import defaultdict def reorganizeString(string: str) -> list: heap = [] hash = {} for i in string: if i in hash: hash[i] += 1 else: hash[i] = 1 for k,v in hash.items(): heapq.heappush(heap, (-v,k)) if v > len(hash): return '' text = [] while 2 <= len(heap): v, k = heapq.heappop(heap) v += 1 v1, k1 = heapq.heappop(heap) v1 += 1 text.append(str(k)) text.append(str(k1)) if v != 0 : heapq.heappush(heap, (v,k)) if v1 != 0: heapq.heappush(heap, (v1,k1)) while heap: v,k = heapq.heappop(heap) text.append(str(k)) return''.join(text) response = reorganizeString("aacab") print(response) response = reorganizeString("aaab") print(response) ```

Esta es mi solución en java. ```java public class ReorganizeString { public static void main(String[] args) { final Scanner scanner = new Scanner(System.in); System.out.println("insert the value to reorganize"); final String str = scanner.nextLine(); System.out.printf("the reorganized string [%s] is: [%s]", str, reorganizeString(str)); } private static String reorganizeString(String str) { final Map<Character, Integer> characterOccurrenceCount = new HashMap<>(); for(char c : str.toCharArray()){ characterOccurrenceCount.put(c, characterOccurrenceCount.getOrDefault(c, 0) + 1); } final PriorityQueue<Map.Entry<Character, Integer>> maxPriorityQueue = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue()); maxPriorityQueue.addAll(characterOccurrenceCount.entrySet()); assert maxPriorityQueue.peek() != null; if(maxPriorityQueue.peek().getValue() > (str.length() + 1)/2) return "the string %s cannot be reordered".formatted(str); StringBuilder reorganizedString = new StringBuilder(); Map.Entry<Character, Integer> prevValue = null; while (!maxPriorityQueue.isEmpty()){ Map.Entry<Character, Integer> currentEntry = maxPriorityQueue.poll(); if(Objects.nonNull(prevValue) && prevValue.getValue() > 0){ maxPriorityQueue.add(prevValue); } reorganizedString.append(currentEntry.getKey()); currentEntry.setValue(currentEntry.getValue() - 1); prevValue=currentEntry; } return reorganizedString.toString(); } } ```

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");
    }

}

Mi solucion con Python, solo cambia en la logica del while y en como crea el heap

import heapq
from collections import defaultdict

def reorganize_string(s: str) -> str:
    counter, max_heap = defaultdict(int), []

    for char in s:
        counter[char] += 1
        # No se puede modificar, porque hay un mismo char mas de la mitad del total 
        if counter[char] > (len(s) + 1) / 2:
            return ""

    # Agregamos los elementos al heap de manera negativa para tener los mayores primero.
    for k, v in counter.items():
        heapq.heappush(max_heap, (-v, k))

    temp_list = []
    while max_heap:
        # Sacamos los dos caracteres más repetidos
        v1, k1 = heapq.heappop(max_heap)
        temp_list.append(k1)
        if max_heap:
            v2, k2 = heapq.heappop(max_heap)
            temp_list.append(k2)
            if  v2 < -1:
                heapq.heappush(max_heap, (v2 + 1, k2))
        # Si todavia hay ocurrencias los regresamos al heap
        if v1 < -1:
            heapq.heappush(max_heap, (v1 + 1, k1))

    return "".join(temp_list)

A mí me quedo mi solución así. Me inventé una cola medio rara con la lista en_espera, pero creo que el objetivo era usar colas de prioridad… x3 😂😅

from typing import List

def reorganize_string(s: str) -> str:
  resultado: str = s[0]
  en_espera: List[str] = []
  
  for c in s[1:]:
    if resultado[-1] == c:
      en_espera.append(c)
    else:
      if len(en_espera) != 0:
        resultado += c
        resultado += en_espera.pop(0)
      else:
        resultado += c
  
  if len(en_espera) != 0:
    return ''
  else:
    return resultado