Java compressing Strings

Question

I need to create a method that receives a String and also returns a String.

Ex input: AAABBBBCC

Ex output: 3A4B2C

Well, this is quite embarrassing and I couldn't manage to do it on the interview that I had today ( I was applying for a Junior position ), now, trying at home I made something that works statically, I mean, not using a loop which is kind of useless but I don't know if I'm not getting enough hours of sleep or something but I can't figure it out how my for loop should look like. This is the code:

public static String Comprimir(String texto){

    StringBuilder objString = new StringBuilder();

    int count;
    char match;

        count = texto.substring(texto.indexOf(texto.charAt(1)), texto.lastIndexOf(texto.charAt(1))).length()+1;
        match = texto.charAt(1);
        objString.append(count);
        objString.append(match);

    return objString.toString();
}

Thanks for your help, I'm trying to improve my logic skills.

Does `ABC` get "compressed" to `1A1B1C` or stay as `ABC`? What about AABC -> 2ABC? — tigrang, May 18 '12 at 06:07
In the input the same alphabet always come together or not. Means can input be of the format AAABBBCCCAACDD?? — Jainendra, May 18 '12 at 06:12
The exam didn't specify. I'd like to do it the hard(best) way :). — Cristian, May 18 '12 at 06:16

n00begon · Answer 1 · 2012-05-18T06:25:25.100

Loop through the string remembering what you last saw. Every time you see the same letter count. When you see a new letter put what you have counted onto the output and set the new letter as what you have last seen.

String input = "AAABBBBCC";

int count = 1;

char last = input.charAt(0);

StringBuilder output = new StringBuilder();

for(int i = 1; i < input.length(); i++){
    if(input.charAt(i) == last){
    count++;
    }else{
        if(count > 1){
            output.append(""+count+last);
        }else{
            output.append(last);
        }
    count = 1;
    last = input.charAt(i);
    }
}
if(count > 1){
    output.append(""+count+last);
}else{
    output.append(last);
}
System.out.println(output.toString());

score 6 · Answer 2 · edited Oct 30 '17 at 11:17

6

You can do that using the following steps:

Create a HashMap
For every character, Get the value from the hashmap -If the value is null, enter 1 -else, replace the value with (value+1)
Iterate over the HashMap and keep concatenating (Value+Key)

edited Oct 30 '17 at 11:17

Mark Rotteveel

100,966
191
140
197

answered May 18 '12 at 06:13

Chander Shivdasani

9,878
20
76
107

11

I don't think this will work AAABBAAA will compress to 6A2B which you cannot uncompress!!! – Chip May 18 '12 at 07:45
1

Make sure the `HashMap` is a `LinkedHashMap` though, as other implementations will mess up the key order. – Matthieu Jul 18 '13 at 16:14
your solution won't work with string like that: "AAABBBCCAA" – Sviatlana Nov 07 '19 at 12:19

score 4 · Answer 3 · answered May 18 '12 at 06:09

use StringBuilder (you did that)
define two variables - previousChar and counter
loop from 0 to str.length() - 1
each time get str.charat(i) and compare it to what's stored in the previousChar variable
if the previous char is the same, increment a counter
if the previous char is not the same, and counter is 1, increment counter
if the previous char is not the same, and counter is >1, append counter + currentChar, reset counter
after the comparison, assign the current char previousChar
cover corner cases like "first char"

Something like that.

Kushal Shinde · Answer 4 · 2018-01-25T04:47:39.697

The easiest approach:- Time Complexity - O(n)

public static void main(String[] args) {
    String str = "AAABBBBCC";       //input String
    int length = str.length();      //length of a String

    //Created an object of a StringBuilder class        
    StringBuilder sb = new StringBuilder(); 

    int count=1;   //counter for counting number of occurances

    for(int i=0; i<length; i++){
        //if i reaches at the end then append all and break the loop
        if(i==length-1){         
            sb.append(str.charAt(i)+""+count);
            break;
        }

        //if two successive chars are equal then increase the counter
        if(str.charAt(i)==str.charAt(i+1)){   
            count++;
        }
        else{
        //else append character with its count                            
            sb.append(str.charAt(i)+""+count);
            count=1;     //reseting the counter to 1
        }
   }

    //String representation of a StringBuilder object
    System.out.println(sb.toString());   

}

more easier would be when we initialize count as 0, then we need only one if condition - for(int i=0;i — coder87, Nov 25 '22 at 12:39

score 3 · Answer 5 · answered May 18 '12 at 06:16

In the count=... line, lastIndexOf will not care about consecutive values, and will just give the last occurence.

For instance, in the string "ABBA", the substring would be the whole string.

Also, taking the length of the substring is equivalent to subtracting the two indexes.

I really think that you need a loop. Here is an example :

public static String compress(String text) {
    String result = "";

    int index = 0;

    while (index < text.length()) {
        char c = text.charAt(index);
        int count = count(text, index);
        if (count == 1)
            result += "" + c;
        else
            result += "" + count + c;
        index += count;
    }

    return result;
}

public static int count(String text, int index) {
    char c = text.charAt(index);
    int i = 1;
    while (index + i < text.length() && text.charAt(index + i) == c)
        i++;
    return i;
}

public static void main(String[] args) {
    String test = "AAABBCCC";
    System.out.println(compress(test));
}

Very nice, I'm going to study all the variables you guys are giving me. I don't want to go through that embarrassment never again. — Cristian, May 18 '12 at 06:20

score 3 · Answer 6 · answered Mar 08 '16 at 07:34

Please try this one. This may help to print the count of characters which we pass on string format through console.

import java.util.*;

public class CountCharacterArray {
   private static Scanner inp;

public static void main(String args[]) {
   inp = new Scanner(System.in);
  String  str=inp.nextLine();
   List<Character> arrlist = new ArrayList<Character>();
   for(int i=0; i<str.length();i++){
       arrlist.add(str.charAt(i));
   }
   for(int i=0; i<str.length();i++){
       int freq = Collections.frequency(arrlist, str.charAt(i));
       System.out.println("Frequency of "+ str.charAt(i)+ "  is:   "+freq); 
   }
     }    
}

Reg · Answer 7 · 2015-12-31T12:59:59.777

2

This is just one more way of doing it.

public static String compressor(String raw) {
        StringBuilder builder = new StringBuilder();
        int counter = 0;
        int length = raw.length();
        int j = 0;
        while (counter < length) {
            j = 0;
            while (counter + j < length && raw.charAt(counter + j) == raw.charAt(counter)) {
                j++;
            }

            if (j > 1) {
                builder.append(j);
            }
            builder.append(raw.charAt(counter));
            counter += j;
        }

        return builder.toString();
    }

edited Dec 31 '15 at 12:59

answered May 18 '12 at 06:22

Reg

10,717
6
37
54

1

Thanks to you mate, I hope you have a nice day. You just got out of bed and you already helped a guy :) – Cristian May 18 '12 at 06:25

score 2 · Answer 8 · answered May 18 '12 at 07:34

Java's not my main language, hardly ever use it, but I wanted to give it a shot :] Not even sure if your assignment requires a loop, but here's a regexp approach:

 public static String compress_string(String inp) {
      String compressed = "";
      Pattern pattern = Pattern.compile("([\\w])\\1*");
      Matcher matcher = pattern.matcher(inp);
      while(matcher.find()) {
         String group = matcher.group();
         if (group.length() > 1) compressed += group.length() + "";
         compressed += group.charAt(0);
      }
      return compressed;
   }

score 2 · Answer 9 · edited Jul 20 '17 at 02:47

The following can be used if you are looking for a basic solution. Iterate through the string with one element and after finding all the element occurrences, remove that character. So that it will not interfere in the next search.

public static void main(String[] args) {
    String string = "aaabbbbbaccc";
    int counter;
    String result="";
    int i=0;
    while (i<string.length()){
        counter=1;
        for (int j=i+1;j<string.length();j++){ 
            System.out.println("string length ="+string.length());  
            if (string.charAt(i) == string.charAt(j)){
                  counter++;
            }
      }
      result = result+string.charAt(i)+counter; 
      string = string.replaceAll(String.valueOf(string.charAt(i)), ""); 
    }
    System.out.println("result is = "+result);
}

And the output will be := result is = a4b5c3

Subhrajyoti Majumder · Answer 10 · 2012-05-18T10:03:21.853

private String Comprimir(String input){
        String output="";
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        for(int i=0;i<input.length();i++){
            Character character=input.charAt(i);
            if(map.containsKey(character)){
                map.put(character, map.get(character)+1);
            }else
                map.put(character, 1);
        }
        for (Entry<Character, Integer> entry : map.entrySet()) {
            output+=entry.getValue()+""+entry.getKey().charValue();
        }
        return output;
    }

One other simple way using Multiset of guava-

import java.util.Arrays;

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;
import com.google.common.collect.Multiset.Entry;

public class WordSpit {
    public static void main(String[] args) {
        String output="";
        Multiset<String> wordsMultiset = HashMultiset.create();
        String[] words="AAABBBBCC".split("");
        wordsMultiset.addAll(Arrays.asList(words));
        for (Entry<String> string : wordsMultiset.entrySet()) {
            if(!string.getElement().isEmpty())
                output+=string.getCount()+""+string.getElement();
        }
        System.out.println(output);
    }
}

Great way of solving it, I'll analyze it step by step. Thanks for your time! — Cristian, May 18 '12 at 06:23
It doesn't work because it won't handle character repeats: `"AAABBBCCAA"` would be `"5A3B2C"` instead of `"3A3B2C2A"`. Moreover, `HashMap` does not preserve key order. Use `LinkedHashMap` instead. — Matthieu, Jul 18 '13 at 16:20

Chaitanya Vardhan · Answer 11 · 2016-10-01T06:28:58.373

consider the below Solution in which the String s1 identifies the unique characters that are available in a given String s (for loop 1), in the second for loop build a string s2 that contains unique character and no of times it is repeated by comparing string s1 with s.

public static void main(String[] args) 
{
    // TODO Auto-generated method stub

    String s = "aaaabbccccdddeee";//given string
    String s1 = ""; // string to identify how many unique letters are available in a string
    String s2=""; //decompressed string will be appended to this string
    int count=0;
    for(int i=0;i<s.length();i++) {
        if(s1.indexOf(s.charAt(i))<0) {
            s1 = s1+s.charAt(i);
        }
    }
    for(int i=0;i<s1.length();i++) {
        for(int j=0;j<s.length();j++) {
            if(s1.charAt(i)==s.charAt(j)) {
                count++;
            }
        }
        s2=s2+s1.charAt(i)+count;
        count=0;
    }

    System.out.println(s2);
}

:-P added explanation – Chaitanya Vardhan Oct 01 '16 at 06:31 — Chaitanya Vardhan, Oct 01 '16 at 06:31

score 1 · Answer 12 · answered Oct 15 '16 at 02:00

It may help you.

public class StringCompresser
{
public static void main(String[] args)
{
    System.out.println(compress("AAABBBBCC"));
    System.out.println(compress("AAABC"));
    System.out.println(compress("A"));
    System.out.println(compress("ABBDCC"));
    System.out.println(compress("AZXYC"));
}

static String compress(String str)
{
    StringBuilder stringBuilder = new StringBuilder();
    char[] charArray = str.toCharArray();
    int count = 1;
    char lastChar = 0;
    char nextChar = 0;
    lastChar = charArray[0];
    for (int i = 1; i < charArray.length; i++)
    {
        nextChar = charArray[i];
        if (lastChar == nextChar)
        {
            count++;
        }
        else
        {
            stringBuilder.append(count).append(lastChar);
            count = 1;
            lastChar = nextChar;

        }
    }
    stringBuilder.append(count).append(lastChar);
    String compressed = stringBuilder.toString();

    return compressed;
} 
}

Output:

3A4B2C
3A1B1C
1A
1A2B1D2C
1A1Z1X1Y1C

score 1 · Answer 13 · answered Aug 31 '18 at 07:17

The answers which used Map will not work for cases like aabbbccddabc as in that case the output should be a2b3c2d2a1b1c1.

In that case this implementation can be used :

private String compressString(String input) {
        String output = "";
        char[] arr = input.toCharArray();
        Map<Character, Integer> myMap = new LinkedHashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && arr[i] != arr[i - 1]) {
                output = output + arr[i - 1] + myMap.get(arr[i - 1]);
                myMap.put(arr[i - 1], 0);
            }
            if (myMap.containsKey(arr[i])) {
                myMap.put(arr[i], myMap.get(arr[i]) + 1);
            } else {
                myMap.put(arr[i], 1);
            }
        }

        for (Character c : myMap.keySet()) {
            if (myMap.get(c) != 0) {
                output = output + c + myMap.get(c);
            }
        }

        return output;
    }

Ankit Sharma · Answer 14 · 2019-04-29T07:40:33.840

1

O(n) approach

No need for hashing. The idea is to find the first Non-matching character. The count of each character would be the difference in the indices of both characters.

for a detailed answer: https://stackoverflow.com/a/55898810/7972621

The only catch is that we need to add a dummy letter so that the comparison for the last character is possible.

private static String compress(String s){
    StringBuilder result = new StringBuilder();
    int j = 0;
    s = s + '#';
    for(int i=1; i < s.length(); i++){
        if(s.charAt(i) != s.charAt(j)){
            result.append(i-j);
            result.append(s.charAt(j));
            j = i;
        }
    }
   return result.toString();
}

edited Apr 29 '19 at 07:40

answered Apr 29 '19 at 07:03

Ankit Sharma

1,626
1
14
21

for taking care of last characters, you can just add a special case before returning the string, look out for my answer. Although your answer is correct, you really don't need # and all, just have simple counter and reset it, whenever the current and next character changes. – Jay Dangar Aug 27 '19 at 13:39

score 0 · Answer 15 · answered Aug 14 '15 at 07:29

The code below will ask the user for user to input a specific character to count the occurrence .

import java.util.Scanner;

class CountingOccurences {

public static void main(String[] args) {

    Scanner inp = new Scanner(System.in);

    String str;
    char ch;
    int count=0;

    System.out.println("Enter the string:");
    str=inp.nextLine();
    System.out.println("Enter th Char to see the occurence\n");
    ch=inp.next().charAt(0);

    for(int i=0;i<str.length();i++)
    {
                if(str.charAt(i)==ch)
        {
            count++;
                }
    }

        System.out.println("The Character is Occuring");
        System.out.println(count+"Times");


}

}

score 0 · Answer 16 · edited Sep 27 '15 at 06:24

public static char[] compressionTester( char[] s){

    if(s == null){
        throw new IllegalArgumentException();
    }

    HashMap<Character, Integer> map = new HashMap<>();
    for (int i = 0 ; i < s.length ; i++) {

        if(!map.containsKey(s[i])){
            map.put(s[i], 1);
        }
        else{
            int value = map.get(s[i]);
            value++;
            map.put(s[i],value);
        }           
    }               
    String newer="";

    for( Character n : map.keySet()){

        newer = newer + n + map.get(n); 
    }
    char[] n = newer.toCharArray();

    if(s.length > n.length){
        return n;
    }
    else{

        return s;               
    }                       
}

score 0 · Answer 17 · edited Mar 06 '16 at 03:35

package com.tell.datetime;

import java.util.Stack;
public class StringCompression {
    public static void main(String[] args) {
        String input = "abbcccdddd";
        System.out.println(compressString(input));
    }

    public static String compressString(String input) {

        if (input == null || input.length() == 0)
            return input;
        String finalCompressedString = "";
        String lastElement="";
        char[] charArray = input.toCharArray();
        Stack stack = new Stack();
        int elementCount = 0;
        for (int i = 0; i < charArray.length; i++) {
            char currentElement = charArray[i];
            if (i == 0) {
                stack.push((currentElement+""));
                continue;
            } else {
                if ((currentElement+"").equalsIgnoreCase((String)stack.peek())) {
                    stack.push(currentElement + "");
                    if(i==charArray.length-1)
                    {
                        while (!stack.isEmpty()) {

                            lastElement = (String)stack.pop();
                            elementCount++;
                        }

                        finalCompressedString += lastElement + "" + elementCount;
                    }else
                    continue;
                }

                else {
                    while (!stack.isEmpty()) {

                        lastElement = (String)stack.pop();
                        elementCount++;
                    }

                    finalCompressedString += lastElement + "" + elementCount;
                    elementCount=0;
                    stack.push(currentElement+"");
                }

            }
        }

        if (finalCompressedString.length() >= input.length())
            return input;
        else
            return finalCompressedString;
    }

}

score 0 · Answer 18 · answered Oct 29 '17 at 08:00

0

public class StringCompression {
    public static void main(String[] args){
        String s = "aabcccccaaazdaaa";

        char check = s.charAt(0);
        int count = 0;

        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == check) {
                count++;
                if(i==s.length()-1){
                System.out.print(s.charAt(i));
                System.out.print(count);
             }
            } else {
                System.out.print(s.charAt(i-1));
                System.out.print(count);
                check = s.charAt(i);
                count = 1;
                if(i==s.length()-1){
                    System.out.print(s.charAt(i));
                    System.out.print(count);
                 }
            }
        }
    }

answered Oct 29 '17 at 08:00

Parth Parikh

11
1
2
8

Please don't just dump code as an answer, add a description on how this solves the question. – Mark Rotteveel Oct 29 '17 at 09:05
Mark Rotteveel gave me -1. But the answer is valid. It will print the correct answer. – Parth Parikh Oct 29 '17 at 23:05
Yes, I gave you a -1, because you shouldn't just dump code, you should explain your solution. – Mark Rotteveel Oct 30 '17 at 11:17

score 0 · Answer 19 · answered Aug 27 '19 at 13:37

 // O(N) loop through entire character array
 // match current char with next one, if they matches count++
 // if don't then just append current char and counter value and then reset counter.
// special case is the last characters, for that just check if count value is > 0, if it's then append the counter value and the last char

 private String compress(String str) {
        char[] c = str.toCharArray();
        String newStr = "";
        int count = 1;
        for (int i = 0; i < c.length - 1; i++) {
            int j = i + 1;
            if (c[i] == c[j]) {
                count++;
            } else {
                newStr = newStr + c[i] + count;
                count = 1;
            }
        }

        // this is for the last strings...
        if (count > 0) {
            newStr = newStr + c[c.length - 1] + count;
        }

        return newStr;
    }

@Cristian, although my answer prints, A3C4, but you can change it easily by changing newStr. It's also solving this problem in O(N) time. — Jay Dangar, Aug 27 '19 at 13:46

score 0 · Answer 20 · answered Aug 30 '20 at 14:35

public class StringCompression {
    public static void main(String... args){
        String s="aabbcccaa";
        //a2b2c3a2

        for(int i=0;i<s.length()-1;i++){
            int count=1;
            while(i<s.length()-1 && s.charAt(i)==s.charAt(i+1)){
                count++;
                i++;
            }
            System.out.print(s.charAt(i));
            System.out.print(count);
        }
        System.out.println(" ");
    }
}

this will output a1b1 for abc. – Engineer May 05 '21 at 14:35 — Engineer, May 05 '21 at 14:35

score 0 · Answer 21 · answered Jan 27 '22 at 21:49

This is a leet code problem 443. Most of the answers here uses StringBuilder or a HashMap, the actual problem statement is to solve using the input char array and in place array modification.

public int compress(char[] chars) {
    int startIndex = 0;
    int lastArrayIndex = 0;
    if (chars.length == 1) {
      return 1;
    }
    if (chars.length == 0) {
      return 0;
    }
    for (int j = startIndex + 1; j < chars.length; j++) {
      if (chars[startIndex] != chars[j]) {

        chars[lastArrayIndex] = chars[startIndex];
        lastArrayIndex++;
        if ((j - startIndex) > 1) {
          for (char c : String.valueOf(j - startIndex).toCharArray()) {
            chars[lastArrayIndex] = c;
            lastArrayIndex++;
          }
        }
        startIndex = j;
      }
      if (j == chars.length - 1) {
        if (j - startIndex >= 1) {
          j = chars.length;
          chars[lastArrayIndex] = chars[startIndex];
          lastArrayIndex++;
          for (char c : String.valueOf(j - startIndex).toCharArray()) {
            chars[lastArrayIndex] = c;
            lastArrayIndex++;
          }
        } else {
          chars[lastArrayIndex] = chars[startIndex];
          lastArrayIndex++;
        }
      }
    }
    return lastArrayIndex;
  }
}

Java compressing Strings

21 Answers21

Linked

Related