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

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

Tomar examen

Programando Reorganize String con Python

Comentarios

Pro Code

student•

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

Pro Code

student•

Ejecutar python 3 online: https://www.tutorialspoint.com/execute_numpy_online.php

Nicolas Guillen

student•

Este recurso me ayudó mucho 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.

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

Aporte en C++, la logica un poco differente al curso:

#include<iostream>
#include<vector>
#include<queue>


std::string reorganize_string(const std::string &input){
	int hash[26];
	std::string output;
	std::priority_queue<std::pair<int, char>, std::vector<std::pair<int,char>>> max_q;

	for(int c=0;c<26;c++){
		hash[c] = 0;
	}
	for(auto c: input){
		hash[c - 'a']++;
	}

	for(int c=0;c<26;c++){
		if(hash[c] != 0){
			max_q.push({hash[c], c + 'a'});
		}
	}
	if(max_q.top().first > (input.size() + 1)/2){
		std::cout << "cant be done" << std::endl;
		return "";
	}
	
	std::pair<int, char> prev = {0, '#'};
	while(!max_q.empty()){
		std::pair<int, char> current = max_q.top();
		max_q.pop();
		output += current.second;
		current.first--;

		if(prev.first){
			max_q.push(prev);
		}

		prev = current;
	}

	return output;
}


int main(){

	std::string input = "aaaabc";
	std::string output = reorganize_string(input);
	std::cout << output << std::endl;

	return 0;
}

John Eduard Meneses González

student•

My solution!!

Miguel Angel Reyes Moreno

student•

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)

Santiago Amaya

student•

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)

Yojan Antonio Pardo Zabala

student•

Esta es mi solución en 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();
    }
}

Hans Arias

student•

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

}

Luis Antonio Ibarra Salgado

student•

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)

Luis Angel Armenta Delgadillo

student•

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

Emilio Sala

student•

está muy bien la idea! pero para casos especiales no daría la respuesta esperada. como por ejemplo "caa" el caracter con más apariciones debería de estar siempre al inicio para aprovechar los inicios y finales.

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

#include<iostream>
#include<vector>
#include<queue>


std::string reorganize_string(const std::string &input){
	int hash[26];
	std::string output;
	std::priority_queue<std::pair<int, char>, std::vector<std::pair<int,char>>> max_q;

	for(int c=0;c<26;c++){
		hash[c] = 0;
	}
	for(auto c: input){
		hash[c - 'a']++;
	}

	for(int c=0;c<26;c++){
		if(hash[c] != 0){
			max_q.push({hash[c], c + 'a'});
		}
	}
	if(max_q.top().first > (input.size() + 1)/2){
		std::cout << "cant be done" << std::endl;
		return "";
	}
	
	std::pair<int, char> prev = {0, '#'};
	while(!max_q.empty()){
		std::pair<int, char> current = max_q.top();
		max_q.pop();
		output += current.second;
		current.first--;

		if(prev.first){
			max_q.push(prev);
		}

		prev = current;
	}

	return output;
}


int main(){

	std::string input = "aaaabc";
	std::string output = reorganize_string(input);
	std::cout << output << std::endl;

	return 0;
}

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)

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

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

}

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)

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

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: Reorganize String