Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Created February 7, 2014 20:01
Show Gist options
  • Save Jeffwan/8870621 to your computer and use it in GitHub Desktop.
Save Jeffwan/8870621 to your computer and use it in GitHub Desktop.
Basic String Compression Input: aabbc Output: a2b2c1 CC 150 - Arrays and Strings
package leetcode;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
/**
* aabcccccaaa --> a2b1c5a3
* PS: like aa repeat is continious... Actually don't need to Use HashMap to statistic -- like book first
*
*
* Still two ways to solve this problem. more efficient
*/
public class Compression {
public static void main(String args[]) {
String str = "aabcccccaaa";
System.out.println(compression(str));
}
/**
* Book frist Solution O(n+k2)
* Same as Two pointer, if char changed, stop and append the char the repeat number
*/
public static String compression(String str) {
StringBuffer sb = new StringBuffer();
char last = str.charAt(0);
int count = 0;
for (int i=0; i< str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
sb.append(last + "" + count);
count = 1; // here count should be 1 but not 0
}
last = str.charAt(i);
}
sb.append(last + "" + count); //reflush the last part
String newStr = sb.toString();
if (newStr.length() < str.length()) {
return newStr;
} else {
return str;
}
}
/**
* My Solution: Store every number frequency and then Reconstruct them use a StringBuffer
* not efficient because of two loop
*/
public static String compression2(String str) {
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
for (int i=0; i<str.length(); i++) {
char value = str.charAt(i);
if(map.containsKey(value)) {
int count = map.get(value) + 1;
map.put(value, count );
} else {
map.put(value, 1);
}
}
// construct string
StringBuffer sb = new StringBuffer();
Set<Entry<Character, Integer>> entrySet = map.entrySet();
Iterator<Entry<Character, Integer>> iterator = entrySet.iterator();
while (iterator.hasNext()) {
Entry<Character, Integer> entry = iterator.next();
sb.append(entry.getKey());
sb.append(entry.getValue());
}
String newStr = sb.toString();
// exclude situation like abc --> a1b1c1
if (newStr.length() < str.length()) {
return newStr;
} else {
return str;
}
}
}
@harishkthedeveloper
Copy link

import java.util.*;

public class HelloWorld{

 public static void main(String []args){
    System.out.println("Hello World");
    String str = "aabbbcccc";
    compare(str);
 }

  public static void compare(String str) {
    
        Map<Character,Integer> stringMap = new HashMap<Character,Integer>();
        
        for(int i = 0 ; i < str.length(); i++) {
            char value = str.charAt(i);
            if (stringMap.containsKey(value)) {
                int count = stringMap.get(value)+1;
                stringMap.put(value,count);
            }else{
                stringMap.put(value,1);
            }
        }
        
        String res = "";
        for (Map.Entry<Character,Integer> entry : stringMap.entrySet()) {
            res = res + ""+entry.getKey() + entry.getValue();
            //System.out.println(""+entry.getKey() + entry.getValue()); 
        } 
        System.out.println(res);
    }

}

@harish71
Copy link

harish71 commented Jan 19, 2023

String str= "aabbcccaaaa";

	char[] c= str.toCharArray();
	char temp=str.charAt(0);
	int count=1;
	StringBuffer sb= new StringBuffer();
	for(int i=0;i<c.length-1;i++) {
		temp=c[i];
			if(temp==c[i+1]) {
				count++;
			}else {
				sb.append(temp+""+count);
				count=1;
			}
		
		
	
		
	}
	sb.append(temp+""+count);
	System.out.println(sb.toString());

o/p: a2b2c3a4

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment