Goldman Sachs Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
static string ReturnString(string inputstring)
{
StringBuilder result = new StringBuilder();
int count = 0;
char previousChar = inputstring[0];
//result += previousChar;
for (int i = 0; i < inputstring.Length; i++)
{
if (previousChar == inputstring[i])
{
count++;
previousChar = inputstring[i];
}
else
{
result= result.Append(previousChar);
result = result.Append(count);
count = 0;
previousChar = inputstring[i];
count++;
}
}
result = result.Append(previousChar);
result = result.Append(count);
return result.ToString();
}
public static String encodeString(String str){
int count = 1;
String str1 = "";
Map<String, Integer> map = new LinkedHashMap<String, Integer>();
for(int i = 0; i < str.length(); i++){
String character = Character.toString(str.charAt(i));
if(map.containsKey(character)){
count++;
map.put(character, count);
continue;
}
else{
count = 1;
map.put(character, count);
}
}
Iterator<Entry<String, Integer>> itr = map.entrySet().iterator();
while(itr.hasNext()){
Entry entry = itr.next();
String key = (String) entry.getKey();
String val = String.valueOf((entry.getValue()));
str1 = str1 + key + (val.equals("1") ? "":val);
}
return str1;
}
string encodedString(string input) {
int n = input.length();
if(n < 2) return input;
char prev = input[0];
int count = 1;
string result = "";
for(int i = 1; i < n; ++i) {
if(input[i] == prev) {
++count;
} else {
result = result + prev;
if(count > 1) result = result + (char)(count + 48);
prev = input[i];
count = 1;
}
}
result = result + prev;
if(count > 1) result = result + (char)(count + 48);
return result;
}
void countText(String in){
StringBuilder builder = new StringBuilder();
for (int i = 0; i < in.length();) {
char temp = in.charAt(i);
int count = 0;
while(in.indexOf(temp, i) != -1) {
temp = in.charAt(i);
i++;
count++;
}
builder.append(temp);
if(count > 1){
builder.append(count);
}
}
System.out.println(builder.toString());
}
Does not work for "wwwwaaadexxxxxxwwww" for instance
correct result: w4a3dex6w4
your result: a7dex6w4
I think it is due to the in.indexOf(temp, i) != -1
Yes you are correct.
It should have been: while(in.indexOf(temp, i) != -1 && (in.indexOf(temp, i)) == i )
public class RunLength {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "wwwwaaadexxxxxx";
for(int i=0;i<str.length();){
char c = str.charAt(i);
int j = str.lastIndexOf(c);
System.out.print(str.charAt(i));
if((j+1)-i>1)
System.out.print((j+1)-i);
i = j+1;
}
}
}
public static String getRunLength(String line) {
LinkedHashSet<Character> characters = new LinkedHashSet<Character>();
for (int i = 0; i < line.length(); i++) {
characters.add(line.charAt(i));
}
StringBuilder result = new StringBuilder();
for (Character character : characters) {
int numChars = 0;
for (int i = 0; i < line.length(); i++) {
if (line.charAt(i) == character) {
numChars++;
}
}
result.append(character);
if (numChars != 1) {
result.append(Integer.toString(numChars));
}
}
return result.toString();
public String encode(String string) {
String tmp = "";
String prev = "";
int counter = 1;
for (int i = 0; i < string.length(); i++) {
String character = Character.toString(string.charAt(i));
if (character.equals(prev)) {
counter++;
} else {
if (counter > 1) {
tmp += prev + counter;
} else {
tmp += prev;
}
counter = 1;
}
prev = character;
if (i == string.length() - 1) {
tmp += prev + counter;
}
}
return tmp;
}
public String encode(String string) {
String tmp = "";
String prev = "";
int counter = 1;
for (int i = 0; i < string.length(); i++) {
String character = Character.toString(string.charAt(i));
if (character.equals(prev)) {
counter++;
} else {
if (counter > 1) {
tmp += prev + counter;
} else {
tmp += prev;
}
counter = 1;
}
prev = character;
if (i == string.length() - 1) {
tmp += prev + counter;
}
}
return tmp;
}
O(n) complexity and O(n) memory:
public static String getRunLengthEncoded(String str){
//handle bad input
if(str == null){
throw new NullPointerException("\"str\" may not be null");
}
if(str.length() == 0){
return str;
}
StringBuilder builder = new StringBuilder();
char[] chars = str.getChars();
char c = chars[0];
int count = 1;
char temp;
for(int i = 1; i < chars.length; i++){
temp = chars[i];
if(c != temp){
builder.append(c);
if(count > 1){
builder.append(Integer.toString(count));
}
c = temp;
count = 1;
}
else{
count++;
}
}
builder.append(c);
if(count > 1){
builder.append(Integer.toString(count));
}
return builder.toString();
}
public static string RunEncoding(string input)
{
Dictionary<char, int> table = new Dictionary<char, int>();
foreach (char character in input)
{
int count = 0;
if (!table.TryGetValue(character, out count))
{
table.Add(character, 1);
}
else
{
table[character] = (int)table[character] + 1;
}
}
string returnVal = string.Empty;
foreach (var item in table)
{
returnVal += string.Format("{0}{1}", item.Key, item.Value > 1 ? item.Value.ToString() : "");
}
return null;
}
Algorithm:
a) Pick the first character from source string.
b) Append the picked character to the destination string.
c) Count the number of subsequent occurrences of the picked character and append the count to destination string.
d) Pick the next character and repeat steps b) c) and d) if end of string is NOT reached.
char *encode(char *src) {
int rLen;
char count[MAX_RLEN];
int len = strlen(src);
/* If all characters in the source string are different,
then size of destination string would be twice of input string.
For example if the src is "abcd", then dest would be "a1b1c1d1"
For other inputs, size would be less than twice. */
char *dest = new char [sizeof(char)*(len*2 + 1)];
int i, j = 0, k;
/* traverse the input string one by one */
for(i = 0; i < len; i++) {
/* Copy the first occurrence of the new character */
dest[j++] = src[i];
/* Count the number of occurrences of the new character */
rLen = 1;
while(i + 1 < len && src[i] == src[i+1]) {
rLen++;
i++;
}
/* Store rLen in a character array count[] */
sprintf(count, "%d", rLen);
/* Copy the count[] to destination */
for(k = 0; *(count+k); k++, j++) {
dest[j] = count[k];
}
}
/*terminate the destination string */
dest[j] = '';
return dest;
}
O(N)
Here is a solution using JS. Same thing could be written using Java:
function RunLengthEncode(s) {
var r = "",
prevChar = s[0],
currentChar, currentCharCount = 1;
for (i = 1; i < s.length; i++) {
currentChar = s.charAt(i);
if (prevChar === currentChar) {
currentCharCount++;
} else {
r += prevChar;
if (currentCharCount !== 1) {
r += currentCharCount;
}
currentCharCount = 1;
prevChar = currentChar;
}
}
r += prevChar;
if (currentCharCount !== 1) {
r += currentCharCount;
}
return r;
}
$("body").html("wwwwaaadexxxxxx: " + RunLengthEncode("wwwwaaadexxxxxx") + "<br> wwwwaaadex:" + RunLengthEncode("wwwwaaadex"));
private static String getRunLengthString( String str)
{
if( str.length() < 2)
return null;
char charToMatch = str.charAt(0);
int charCount = 0;
StringBuilder resultBuilder = new StringBuilder();
resultBuilder.append(charToMatch);
for( int i =0 ;i< str.length(); i ++)
{
if( charToMatch == str.charAt(i))
charCount +=1;
else
{
charToMatch = str.charAt(i);
resultBuilder.append(charCount);
resultBuilder.append(charToMatch);
charCount = 1;
}
}
resultBuilder.append(charCount);
return resultBuilder.toString();
}
void runLenEncStr(char sample[250])
{
int count =0,j=0,k=0;
char encArr[250];
for(int i=0;i<strlen(sample);i++)
{
j=i+1;
if(sample[i] == sample[j])
{
count++;
j++;
continue;
}
else
{
encArr[k] = sample[i-count];
if(count!=0)
encArr[++k] = count+1+'0';
count = 0;
}
k++;
encArr[k] = '\0';
}
for(int i=0;i<strlen(encArr);i++)
cout << encArr[i];
}
char[] str = "wwwwaaadexxxxxx".toCharArray();
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < str.length;) {
stringBuilder.append(str[i]);
int k = i + 1;
int count = 1;
while (k < str.length && str[i] == str[k]) {
k++;
count++;
}
if (count > 1) {
stringBuilder.append(count);
}
i = k;
}
System.out.println(stringBuilder);
public static void main(String[] args) {
String inputstring = "wwwwaassddsseerrwwww";
String outputstring = "";
int count =0 ;
char a = inputstring.charAt(0);
for (int i = 1; i< inputstring.trim().length();i++)
{
if (inputstring.charAt(i) == a)
{
count++;
}
else
{
outputstring = outputstring.concat(Character.toString(a));
outputstring = outputstring.concat(Integer.toString(count));
a = inputstring.charAt(i);
count = 1;
}
}
outputstring = outputstring.concat(Character.toString(a));
outputstring = outputstring.concat(Integer.toString(count));
System.out.println("Output :" + outputstring);
}
public class EncodeString {
public static void main(String[] args) {
String str = "aassscssssssssssssssssssvvvvvvvvvv";
encodeString(str);
}
private static void encodeString(String str) {
char[] ch = str.toCharArray();
int count = 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (str.length() != i + 1 && ch[i] == ch[i + 1]) {
count++;
} else if (count == 1) {
sb.append(ch[i]);
count = 1;
} else {
sb.append(ch[i]).append(count);
count = 1;
}
}
System.out.println(sb);
}
}
public class Goldman {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str="wwwwaaadexxxxxxfgttsgge";
int count=1;
for (int i = 0; i < str.length()-1; i++) {
if(str.charAt(i+1)==str.charAt(i)){
count++;
}
else{
if(count>1){
System.out.print(str.charAt(i));
System.out.print(count);
}
else{
System.out.print(str.charAt(i));
}
count=1;
}
}
if(count>1){
System.out.print(str.charAt(str.length()-1));
System.out.print(count);
}
else{
System.out.print(str.charAt(str.length()-1));
}
}
}
public class Repeat {
public static void main(String[] args) {
String str = "aaabbbcdcdertyukkoooo", output = "";
char[] arr = str.toCharArray();
int count = 1, i = 0, j = 0;
for (i = 0; i < arr.length; i++) {
count = 1;
if (i == arr.length) {
output += arr[i];
break;
}
for (j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j])
count++;
else
break;
}
if (count > 1)
output += arr[i] + "" + count;
else
output += arr[i] + "";
i = j - 1;
}
System.out.println(output);
}
}
public class Repeat {
public static void main(String[] args) {
String str = "wwwwaaadexxxxxxfgttsgge", output = "";
char[] arr = str.toCharArray();
int count = 1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
count++;
} else {
if (count > 1)
output += arr[i] + "" + count;
else
output += arr[i] + "";
count = 1;
}
}
if (count > 1)
output += arr[arr.length - 1] + "" + count;
else
output += arr[arr.length - 1] + "";
System.out.println(output);
}
}
Check this out.
/*
Given an input string, write a function that returns the Run Length Encoded string for the input string.
For example, if the input string is “wwwwaaadexxxxxx”,
then the function should return “w4a3dex6″.
*/
#include <stdio.h>
int main(void)
{
//char *str="wwwwaaadexxxxxx";
char *str="wwwwaaadexxxxxxwwww";
char *t=str,*p=str;
char newstring[500];
int rep_count=0,start=0,flag=0;
newstring[0] = '\0';
while(*t)
{
start=t-str;
rep_count=1;
flag=0;
p++;
while(*t==*p)
{
rep_count++;
p++;
t++;
flag=1;
}
if(flag)
{
char temp[20];
int len=0;
sprintf(temp,"%d",rep_count);
len = strlen(newstring);
newstring[len] = *t;
newstring[len+1]='\0';
strcat(newstring,temp);
}
else
{
int len=strlen(newstring);
newstring[len]= *t;
newstring[len+1] = '\0';
}
t++;
}
printf("%s\n",newstring);
return 0;
}
public class Main {
static String encodeString (String input) {
StringBuilder sb = new StringBuilder();
int cnt = 0;
char lastChar = (char) -1;
char thisChar = (char) -1;
for (int i=0;i<input.length();i++) {
thisChar = input.charAt(i);
if (lastChar != thisChar) {
if (cnt > 1) {
sb.append(cnt);
}
sb.append(thisChar);
cnt =0;
}
cnt++;
lastChar = thisChar;
}
if (cnt>1) {
sb.append(cnt);
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(encodeString("wwwwaaadexxxxxx"));
}
}
Here's a dynamic programming based solution sans any loops
import java.util.HashMap;
import java.util.Map;
public class EncodeString {
private static Map<String, String> memo = new HashMap<String, String>();
private static String encodeString(String string) {
String returnValue;
if (memo.containsKey(string)) {
returnValue = memo.get(string);
} else {
if (string.length() == 0) {
return "";
} else if (string.length() == 1) {
returnValue = string.concat("1");
} else {
String encodedSubstring = encodeString(string.substring(1));
if (string.substring(0, 1).equals(
encodedSubstring.substring(0, 1))) {
returnValue = new StringBuilder()
.append(encodedSubstring.charAt(0))
.append(encodedSubstring.charAt(1) - '0' + 1)
.append(encodedSubstring.substring(2)).toString();
} else {
returnValue = new StringBuilder()
.append(string.substring(0, 1)).append('1')
.append(encodedSubstring).toString();
}
memo.put(string, returnValue);
}
}
return returnValue;
}
public static void main(String[] args) {
System.out.println(encodeString("apple"));
memo.clear();
System.out.println(encodeString("mango"));
memo.clear();
System.out.println(encodeString("aaaa"));
memo.clear();
System.out.println(encodeString(""));
memo.clear();
System.out.println(encodeString("a"));
memo.clear();
System.out.println(encodeString("wwwwaaadexxxxxxwwww"));
memo.clear();
System.out.println(encodeString("aa"));
memo.clear();
System.out.println(encodeString("aaa"));
memo.clear();
System.out.println(encodeString("aaaa"));
memo.clear();
System.out.println(encodeString("aabaabaa"));
memo.clear();
System.out.println(encodeString("aabbcbbcaa"));
memo.clear();
}
}
package main
import "fmt"
func main(){
s1 := "wwwwaaadexxxxxx"
s2 := ""
counter := 0
for i:= 0; i< len(s1); i++{
if len(s2) > 0 && s2[len(s2)-1] == s1[i] {
counter ++
} else {
if counter > 1 {
s2 = fmt.Sprint(s2,counter)
}
counter = 1
s2 = fmt.Sprint(s2,s1[i:i+1])
}
}
if counter > 1 {
s2 = fmt.Sprint(s2,counter)
}
fmt.Println(s2)
}
public class EncodeString {
public static void main(String[] args) {
System.out.println(encodeStringMine("wwwwaaadexxxxxx"));
System.out.println(encodeStringMine("wwwwaaadexxxxxxtwwww"));
System.out.println(encodeStringMine("wwwwaaadexxxxxxtwwwwy"));
}
public static String encodeStringMine(String str) {
int count = 1;
String sb = new String();
for (int i = 0; i < str.length(); i++) {
String str1 = str.substring(i, i + 1);
if (sb.length() > 0) {
if (str1.equals(sb.substring(sb.length() - 1, sb.length()))) {
count++;
} else {
if(count==1){
sb = sb + str1;
}else{
sb = sb + count + str1;
}
count = 1;
}
} else {
sb = str1;
}
}
if(count==1){
//do nothing
}else{
sb += count;
}
return sb;
}
}
we can do in C Language Easily...
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int n,i,count=1;
char ch,str[20];
gets(str);
n=strlen(str);
for(i=0;i<n;i++){
if(str[i]==str[i+1])
count++;
else{
ch=str[i];
if(count==1)
printf("%c",ch);
else
printf("%c%d",ch,count);
count=1;
}
}
return 0;
}
Run time O(n) space used O(n)
import java.io.*;
import java.util.*;
public class rle{
public static String convert(String str)
{
String str1 = new String();
char a[] = str.toCharArray();
int count=1;
str1+=a[0];
for(int i=1;i<=str.length();i++)
{
if(i<str.length())
{
if(a[i]==a[i-1])
{
count++;
}
if(a[i]!=a[i-1])
{
str1+=count;
count=1;
str1+=a[i];
}
}
else
{
str1+=count;
}
}
return str1;
}
public static void main(String args[]) throws InterruptedException
{
Scanner ip=new Scanner(System.in);
String str = ip.nextLine();
String str1 = convert(str);
System.out.println(str1);
}
}
class EncodeString{
static String encode(String s){
if(s == null || s.length() == 0 || s.equals("")){
return "";
}
StringBuffer encodedString = new StringBuffer("" + s.charAt(0));
char currRepeatedChar = s.charAt(0);
int count = 1;
for(int i = 1; i < s.length(); i++){
if(s.charAt(i) != currRepeatedChar){
encodedString.append("" + count + s.charAt(i));
count = 1;
currRepeatedChar = s.charAt(i);
continue;
}
count++;
}
encodedString.append("" + count);
return encodedString.toString();
}
public static void main(String args[]){
String s = "wwwwaaadexxxxxx";
System.out.println(encode(s));
}
}
package com.dhruv.gs;
import java.util.Scanner;
public class EncodedString {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter string to check shorted palindrome:");
String st1 = in.nextLine();
String st2 ="";
for(int i=0;i<st1.length();){
int count = 1;
while(i<st1.length()-1 && st1.charAt(i)== st1.charAt(i+1)){
count++;
i++;
}
st2=st2+st1.charAt(i)+count;
i++;
while(i<st1.length()-1 && st1.charAt(i)!= st1.charAt(i+1)) {
st2=st2+st1.charAt(i);
i++;
}
}
System.out.println(st2);
}
}
public static void main(String[] args){
String str = "wwwwaaadexxxxxxwwww";
String newStr = str+" ";
String finalStr="";
int charCount=1;
for(int i = 0; i< newStr.length() - 1; i++){
if(newStr.charAt(i) == newStr.charAt(i+1)){
charCount += 1;
}else{
if(charCount == 1){
finalStr = finalStr+ newStr.charAt(i);
}else{
finalStr = finalStr+ newStr.charAt(i)+charCount;
}
charCount=1;
}
}
System.out.println(finalStr);
}
public static void main(String[] args) {
String str = "wwwwwwaaaeggh";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); ) {
int count = 1;
char c = str.charAt(i);
int j = i;
while (j < str.length() - 1 && str.charAt(j) == str.charAt(j + 1)) {
count++;
j++;
}
sb.append(c).append(count);
i += count;
}
System.out.println(sb.toString());
}
public class NewTest {
public static void main(String arg[])
{
String input = "wwwwaaadexxxxxx";
String output = stringManipulate(input);
System.out.println("output is : " + output);
}
public static String stringManipulate(String str)
{
int cnt = 1;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < str.length() ; i++)
{
sb.append(str.charAt(i));
for(int j = i+1 ; j <str.length() ; j++)
{
if(str.charAt(i) == str.charAt(j))
{
cnt++;
i++;
}
else
{
break;
}
}
if(cnt != 1)
sb.append(String.valueOf(cnt));
cnt = 1;
}
return sb.toString();
}
}
public class NewTest {
public static void main(String arg[])
{
String input = "wwwwaaadexxxxxx";
String output = stringManipulate(input);
System.out.println("output is : " + output);
}
public static String stringManipulate(String str)
{
int cnt = 1;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < str.length() ; i++)
{
sb.append(str.charAt(i));
for(int j = i+1 ; j <str.length() ; j++)
{
if(str.charAt(i) == str.charAt(j))
{
cnt++;
i++;
}
else
{
break;
}
}
if(cnt != 1)
sb.append(String.valueOf(cnt));
cnt = 1;
}
return sb.toString();
}
}
public class NewTest {
public static void main(String arg[])
{
String input = "wwwwaaadexxxxxx";
String output = stringManipulate(input);
System.out.println("output is : " + output);
}
public static String stringManipulate(String str)
{
int cnt = 1;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < str.length() ; i++)
{
sb.append(str.charAt(i));
for(int j = i+1 ; j <str.length() ; j++)
{
if(str.charAt(i) == str.charAt(j))
{
cnt++;
i++;
}
else
{
break;
}
}
if(cnt != 1)
sb.append(String.valueOf(cnt));
cnt = 1;
}
return sb.toString();
}
}
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Set;
public class CountLetter {
public static String getCountLetter(String string){
LinkedHashMap<String,Integer> map=new LinkedHashMap<String,Integer>();
int length=string.length();
int count=1;
String temp="";
char ch=' ';
for(int i=0;i<length;i++)
{
ch=string.charAt(i);
System.out.println(ch);
if(map.containsKey(ch+""))
{
count=map.get(ch+"");
count++;
System.out.println(count);
map.put(ch+"",count);
}
else{
map.put(ch+"",1);
}
}
System.out.println(map);
Set<String> set=map.keySet();
for(String key:set)
{
int value=map.get(key);
if(value==1)
{
temp=temp+key;
}
else{
temp=temp+key+value;
}
}
return temp;
}
public static void main(String[] args)
{
System.out.println(getCountLetter("aabbbbcdd"));
}
}
import java.util.*;
public class Count {
public static void main(String[] args) {
String str1 = "wwwwrrrrxxxde";
char ch[] = str1.toCharArray();
int l = ch.length;
int c = 1;
HashSet set = new LinkedHashSet();
HashMap map = new LinkedHashMap();
for (int i = 0; i < l; i++) {
char ch2 = ch[i];
boolean b = set.add(ch2);
if (b == false) {
c++;
map.put(ch2, c);
} else {
c = 1;
map.put(ch2, null);
}
}
List list = new ArrayList();
Set set1 = map.entrySet();
Iterator it = set1.iterator();
while (it.hasNext()) {
Object ob = it.next();
Map.Entry entry = (Map.Entry) ob;
Object ob1 = entry.getKey();
Object ob2 = entry.getValue();
list.add(ob1);
if (ob2 != null) {
list.add(ob2);
}
}
for(int i=0;i<list.size();i++)
{
System.out.println(list.get(i));
}
}
}
import java.util.*;
public class Count {
public static void main(String[] args) {
String str1 = "wwwwrrrrxxxde";
char ch[] = str1.toCharArray();
int l = ch.length;
int c = 1;
HashSet set = new LinkedHashSet();
HashMap map = new LinkedHashMap();
for (int i = 0; i < l; i++) {
char ch2 = ch[i];
boolean b = set.add(ch2);
if (b == false) {
c++;
map.put(ch2, c);
} else {
c = 1;
map.put(ch2, null);
}
}
List list = new ArrayList();
Set set1 = map.entrySet();
Iterator it = set1.iterator();
while (it.hasNext()) {
Object ob = it.next();
Map.Entry entry = (Map.Entry) ob;
Object ob1 = entry.getKey();
Object ob2 = entry.getValue();
list.add(ob1);
if (ob2 != null) {
list.add(ob2);
}
}
for(int i=0;i<list.size();i++)
{
System.out.println(list.get(i));
}
}
}
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
string str="wwwaaadesxxxxgggggaaaaa";
int i,count=1;
int len=str.length();
string result="";
for(i=1;i<=len;i++)
{
if(str[i]==str[i-1])
count++;
else
{
result+=char(str[i-1]);
if(count>1)
result+=char(count+48);
count=1;
}
}
cout<<result;
}
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
string str="wwwaaadesxxxxgggggaaaaa";
int i,count=1;
int len=str.length();
string result="";
for(i=1;i<=len;i++)
{
if(str[i]==str[i-1])
count++;
else
{
result+=char(str[i-1]);
if(count>1)
result+=char(count+48);
count=1;
}
}
cout<<result;
}
Java Solution simple and efficient 0(n)
public static void EncodeString(String str) {
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
String s = "";
char[] ch = str.toCharArray();
for (int i = 0; i < str.length(); i++) {
if (map.containsKey(ch[i])) {
map.put(ch[i], map.get(ch[i]) + 1);
} else
map.put(ch[i], 1);
}
for (Map.Entry<Character, Integer> kv : map.entrySet()) {
if (kv.getValue() != 1)
s += kv.getKey() + "" + kv.getValue();
else
s += kv.getKey();
}
System.out.println(s);
}
static void count(String str) {
char[] chrs = str.toCharArray();
int count = 1;
StringBuilder res = new StringBuilder();
for (int i = 1; i <= chrs.length; i++) {
if (i != chrs.length && chrs[i] == chrs[i - 1]) {
count++;
} else {
res.append(chrs[i - 1]);
if (count > 1) {
res.append(count);
}
count = 1;
}
}
System.out.println(res.toString());
}
import java.io.*;
public class LengthEncodedString {
public static void main(String args[]) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String s = reader.readLine();
StringBuilder sb = new StringBuilder();
for(int i=0;i<s.length();i++) {
int count = 1;
sb.append(s.charAt(i));
while(i<s.length()-1 && s.charAt(i)==s.charAt(i+1)) {
count++;
i = i+1;
}
if(count>1) {
sb.append(count);
}
}
System.out.println(sb);
}
}
public static StringBuilder encodedString(String str) {
char[] ch = str.toCharArray();
StringBuilder builder = new StringBuilder();
int count = 0;
for (int i = 0; i < str.length()-1; i++) {
char c = ch[i];
count++;
if (c!=ch[i+1]) {
builder.append(c);
builder.append(count);
count = 0;
}
}
builder.append(ch[str.length()-1]);
builder.append(count+1);
return builder;
}
public static StringBuilder encodedString(String str) {
char[] ch = str.toCharArray();
StringBuilder builder = new StringBuilder();
int count = 0;
for (int i = 0; i < str.length()-1; i++) {
char c = ch[i];
count++;
if (c!=ch[i+1]) {
builder.append(c);
builder.append(count);
count = 0;
}
}
builder.append(ch[str.length()-1]);
builder.append(count+1);
return builder;
}
public static StringBuilder encodedString(String str) {
char[] ch = str.toCharArray();
StringBuilder builder = new StringBuilder();
int count = 0;
for (int i = 0; i < str.length()-1; i++) {
char c = ch[i];
count++;
if (c!=ch[i+1]) {
builder.append(c);
builder.append(count);
count = 0;
}
}
builder.append(ch[str.length()-1]);
builder.append(count+1);
return builder;
}
Sorry for no name in the above code run time O(n) and space used O(n)
- Karan Tankshali November 11, 2014