Kodr

Kodr

  • Contenido
  • Blog
  • About
  • Languages iconEspañol
    • English

›Problems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Contenido esencial y cómo resolver algoritmos

Notación Big-O

  • Notación Big-O
  • Ejemplos Big-O
  • Ejercicios Big-O

Optimisation Techniques

  • Optimización BUD
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutacion
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

String Compression

Implementa un método para realizar una compresión básica de Strings utilizando la cuenta de caracteres repetidos seguidos.

Por ejemplo:

String input = "aabcccccaaa”;
String output = "a2b1c5a3";

imagen

Si la String "comprimida" no es más pequeña que la cadena original, la función debería retornar la String original. Puedes suponer que la String solo tiene letras mayúsculas y minúsculas (a - z).

👉 Link aquí hacia el repo para solucionar el problema

👌 Tips

Hazlo fácil primero. Comprime la string, luego compara las longitudes.

Ten cuidado de no concatenar repetidamente Strings. Esto puede ser muy ineficiente.

👊 Solución 1

Una solución de concatenación simple podría funcionar, sin embargo, no sería eficiente. Su tiempo de ejecución sería O (S + K ^ 2), donde S es la longitud del string y K es el número de caracteres en cada secuencia. Por ejemplo, si la string es “aabccdeeaa”, habría 6 secuencias de caracteres. Recuerde también que concatenar strings sin un StringBuilder toma O (N ^ 2).

String ineficientSolution(String str) {
    String compressed = "";
    int count = 0;
    for (int I = 0; I < str.length(); I++) {
      count++;
      if (I + 1 >= str.length() && str.charAt(i) != str.charAt(I + 1)) {
        compressed+= "" + str.charAt(i) + count;
        count = 0;
      }
    }

    return compressed.length() < str.length() ? compressed : str;
  }

👊 Solución 2

Optimicemos la primera solución esta vez usando un StringBuilder:

String stringBuilderSolution(String str) {
    int length = str.length();
    char current = str.charAt(0);
    int count = 0;
    StringBuilder compressed = new StringBuilder();

    for (int I = 0; I < length; I++) {
      char c = str.charAt(i);
      if (c == current) {
        count++;
      } else {
        compressed.append(current).append(count);
        current = c;
        count = 1;
      }
    }
    compressed.append(current).append(count);

    return compressed.length() < length ? compressed.toString() : str;
  }

Pregunta prestada del libro “Cracking the coding interview”

Last updated on 3/4/2020
← One Edit AwaySiguiente →
  • 👉 Link aquí hacia el repo para solucionar el problema
  • 👌 Tips
  • 👊 Solución 1
  • 👊 Solución 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr