Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Arrays & Strings

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

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

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • 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

Implement a method to perform basic string compression using the counts of repeated characters.

For example, the string

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

imagen

If the “compressed” string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

👉 Link here to the repo to solve the problem

👌 Tips

Do the easy thing first. Compress the string, then compare the lengths.

Be careful you are not repeatedly concatenating strings together. This can be very inefficient.

👊 Solution 1

A simple solution concatenating could work, however it would not be efficient. Its runtime would be O (S + K ^ 2), where S is the length of the String and K is the number of character sequences. For example, if the String is "aabccdeeaa" there would be 6 character sequences. Remember also that concatenating strings without a StringBuilder takes 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;
  }

👊 Solution 2

Let’s optimise the first solution this time using a 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;
  }

Borrowed question from the book “Cracking the coding interview”

Last updated on 3/4/2020
← One Edit AwayRotate Matrix →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
  • 👊 Solution 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr