Amazon Interview Question Software Engineer / Developers
this prog works
public class Trystring {
/**
* @param args
*/
public static void main(String[] args) {
String str= "aaaabbcccc";
StringBuffer str1 = new StringBuffer(str);
System.out.println("Input string is "+str1);
char prev = str1.charAt(0);
char curr;
int count=1,prev_index=0;
for(int i=1;i<str1.length();i++)
{
curr= str1.charAt(i);
if(prev==curr)
count++;
else
{
if(count>2)
{
int offset= prev_index+count;
str1.delete(prev_index+1,offset);
str1.insert(prev_index+1, count);
count=1;
prev = curr;
prev_index = prev_index+2;
i=prev_index;
}
else
{
str1.deleteCharAt(prev_index+1);
str1.insert(prev_index+1, count);
count=1;
prev=curr;
prev_index=prev_index+2;
}
}
if(i==(str1.length()-1))
{
int offset= prev_index+count;
str1.delete(prev_index+1,offset);
str1.insert(prev_index+1, count);
}
}
System.out.println("Output string is " +str1);
}
}
A simple choice is to scan from one end using normal "two-pointer-string-inplace-delete" way.
But the had point is here:
abcabcaaaaaaaaaaaaabc -> a1b1c1a1b1c1a13b1c1
You cannot normally start from any end.
I will do such thing to fix:
1. first scan, for every substring like "aaaa" other than "a", compress to "a4", leave any "a1" untouched.
2. second scan, from end to start, using two pointer, inplace move all the space to the front, characters to the tail.
3. third scan, from start to end, using two pointer, inplace move all the characters to the front, unfold "a"s to "a1"s on the way.
<pre lang="c++" line="1" title="CodeMonkey89025" class="run-this">//Using Recursion
#include<iostream>
#include<string.h>
using namespace std;
char b[100];
static int noof_times=1,index=0;
char compress(char *a,char c,int p,int ,int )
{
if(p==-1)return c;
char t=compress(a,a[p],p-1,index,noof_times);
if(t==c)noof_times++;
else
{
a[index++]=t;
a[index++]=noof_times+48;
noof_times=1;
}
return c;
}
int main()
{
cout<<"enter the String ;";
cin.getline(b,100);
int p=strlen(b)-1;
char c=compress(b,b[p],p-1,index,noof_times);
if(noof_times>1)
{
b[index++]=b[p];
b[index++]=noof_times+48;
}
b[index]='\0';
cout<<b;
}
</pre><pre title="CodeMonkey89025" input="yes">aaabbbaaaaa</pre>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,count[20],i,j;
char a[200];
gets(a);
n=strlen(a);
for(i=0;i<n;i++)
{
count[i]=1;
}
i=0;
j=0;
while(i<n&&j<n)
{
if(a[i]==a[i+1])
{
i++;
count[j]++;
continue;
}
else
{
cout<<a[j];
if(count[j]>1)
cout<<count[j];
i++;
j=i;
continue;
}
}
return 0;
}
As far as I understood string abc will be converted to a1b1c1. I think may be it should be abc, because in a worst case it does the thing opposite to compression.
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
void shift_string(char *,int,int);
void main()
{
char *s;
clrscr();
cout<<"\nEnter a string: ";
cin>>s;
int i=0,j=0,cnt;
char ch;
/*int len;
while(*(s+i)!='\0')
i++;
len=i;*/
i=0;
int k,l;
while(*(s+i)!='\0')
{
j=i;
ch=*(s+j);
cnt=0;
while(*(s+j+1)==ch)
{
j++;
cnt++;
}
cnt++;
if(cnt>1)
{
*(s+i+1)=cnt+'0';
//i=i+cnt;
//cout<<"\nHere atleast";
k=i+cnt;
l=cnt-2;
shift_string(s,k,l);
i=i+2;
}
else
i++;
}
cout<<endl<<s;
getch();
}
void shift_string(char *s,int k,int l)
{
//cout<<"\nIs it coming here?";
while(*(s+k)!='\0')
{
*(s+(k-l))=*(s+k);
k++;
}
*(s+k-l)='\0';
//cout<<"\nCheck"<<s;
//*(s+k)='\0';
}
#include <stdio.h>
#include <stdlib.h>
// can count upto 999 occurances
#define NDIGIT 4
// squeeze input string, replacing multiple occurances
// of a character with count
void squeeze(char s[]) {
int i, j, k, count;
char t[NDIGIT];
if(s[0]=='\0')
return;
// first char is taken as-is, proceed from second onwards
for(i=j=count=1; s[j]!='\0'; j++, count++) {
// different char
if(s[j-1]!=s[j]) {
itoa(count, t, NDIGIT);
k = strlen(t);
strncpy(s+i, t, k);
i += strlen(t);
s[i++] = s[j];
count = 0;
}
}
itoa(count, t, NDIGIT);
strcpy(s+i, t);
}
int main() {
char s[] = "aabbbccc";
squeeze(s);
printf("%s\n", s);
return 0;
}
public class StringCompression {
public String compress(String input) {
char[] cs = input.toCharArray();
char temp = cs[0];
int i = 0, j = 0, count = 0, len = cs.length;
while(j < len) {
cs[i++] = temp;
while (j < len && temp == cs[j]) {
j++;
count++;
}
if(j < len)
temp = cs[j++];
cs[i++] = String.valueOf(count).charAt(0);
count = 1;
}
return new String(cs, 0, i);
}
public static void main(String[] args) {
StringCompression compression = new StringCompression();
System.out.println(compression.compress("aabbbccc"));
}
}
This is some basic code. Needs to be modified if there are more that 9 continuous chars.(e.g won't work for aabbbbbbbbbbccc)
public class StringCompress {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String line = " aabbcccccdd";
int count=0;
int b=0;
StringBuilder res = new StringBuilder();
for(int i = 0 ; i<line.length(); i++){
if(line.charAt(i) == ' ')continue;
count = 1;
b=i+1;
res.append(line.charAt(i));
while(b<line.length() && line.charAt(b) == line.charAt(i)){
count++;
b++;
i++;
}
if(count == 1){
System.out.println("Invalid Input");
break;
}
res.append(count);
}
if(line.length() >= res.length()){
if(count != 1)
System.out.println("Compressed String : "+res);
}
}
}
<pre lang="c" line="1" title="CodeMonkey39225" class="run-this">#include <stdio.h>
void strCompress (char* pInputStr)
{
int i=0, k=1;
int count = 0;
char charCh = pInputStr [i];
while (pInputStr [i] != '\0')
{
if (charCh == pInputStr [i])
{
count ++;
}
else
{
pInputStr [k-1] = charCh;
charCh = pInputStr [i];
pInputStr [k] = count + '0';
k = k + 2;
count = 1;
}
i ++;
}
pInputStr [k-1] = charCh;
charCh = pInputStr [i];
pInputStr [k] = count + '0';
pInputStr [k +1] = '\0';
}
int main ()
{
char str [100];
memset (str, 0x00, 100);
gets (str);
printf ("Before: %s\n", str);
strCompress (str);
printf ("After: %s\n", str);
return 0;
}
</pre>
public class compress {
public void compress_string(StringBuffer sb)
{
int count = 1;
char prevChar = sb.charAt(0);
int copyPos = 0;
for (int i = 1;i<sb.length();i++)
{
char curChar = sb.charAt(i);
if (curChar == prevChar)
{
count++;
}
else
{
//copy char and count
sb.setCharAt(copyPos, prevChar);
if (count>1)
{
String s = Integer.toString(count);
int len = s.length();
int index = 0;
while (len>0)
{
copyPos++;
sb.setCharAt(copyPos, s.charAt(index));
len--;
index++;
}
}//if
//set values for next iteration
prevChar = curChar;
count = 1;
copyPos++;
}//else
}//for
//for the last set of character
sb.setCharAt(copyPos, prevChar);
if (count>1)
{
//char charCount = Character.forDigit(count, 10);
String s = Integer.toString(count);
int len = s.length();
int index = 0;
while (len>0)
{
copyPos++;
sb.setCharAt(copyPos, s.charAt(index));
len--;
index++;
}
}
sb.setLength(copyPos+1);
System.out.println("Compressed string is:"+sb);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
compress C = new compress();
StringBuffer s = new StringBuffer("aabbbbbbbbbbccc");
//StringBuffer s = new StringBuffer("aabbbccc");
C.compress_string(s);
}
}
<pre lang="java" line="1" title="CodeMonkey29152" class="run-this">
public class StringManipulator {
/**
* @param args
*/
public static void main(String[] args) {
String line = "aabbbcc";
String newString = getNumberOfWords(line);
System.out.println("\nCompressed string:\t"+newString);
}
private static String getNumberOfWords(String line) {
StringBuffer newLine = new StringBuffer(line);
int start = 0;
int index = start+1;
for(start = 0; start<newLine.length(); start+=2){
index = start+1;
int count = 1;
System.out.println("Starting with string:\t"+newLine);
try{
while((newLine.charAt(start) == newLine.charAt(index))){
newLine.deleteCharAt(index);
System.out.println("trimmed string:\t"+newLine);
count++;
}
newLine.insert(index, count);
System.out.println("compressed string:\t"+newLine);
} catch(StringIndexOutOfBoundsException e){
newLine.append(count);
}
}
return newLine.toString();
}
}
</pre>
public class Stringcomp {
public static void main(String[] args) {
String a = "abcccccccccccccccccccccccccccccccccccdefg";
if(a.length()<1)
{
System.out.println("Error, not a valid string");
System.exit(1);
}
StringBuffer str = new StringBuffer(a);
int k=1,cur_len=0,i=0;
while(i<str.length())
{
str.setCharAt(k-1, str.charAt(i));
Integer count=1;
while(i<str.length()-1 && (str.charAt(i)==str.charAt(i+1)) )
{
count++;
i++;
}
if(count==1)
{
str.insert(k,count);
k = k+2;
cur_len = cur_len+count;
cur_len++;
i = cur_len;
}
else
{
int add_off = count.toString().length()+1;
str.deleteCharAt(k);
str.insert(k,count);
k = k+add_off;
cur_len = cur_len+count;
cur_len = cur_len + count.toString().length()-1;
i=cur_len;
}
}
str.setLength(k-1);
System.out.println(str.toString());
}
}
even works for strings like abc or just a.
In my opinion, string builder or string buffer usage should be okay, as long as you're not using as an additional storage. You can operate on Strings directly in Java anyways, since they're immutable.
e.g. StringBuffer newString = new StringBuffer(<size>); // Not okay
StringBuffer newString = new StringBuffer(originalString); // should be okay.
Correct me if I am wrong
public static void main(String... args)
{
String str="aaabcccccc";
char first=str.charAt(0);
int count=1;
StringBuilder s=null;
for(int i=1;i<str.length();i++)
{
char next=str.charAt(i);
if(first==next)
count++
else
{
s=s.append(first).append(count);
count=1;
}
first=next;
}
System.out.println(s);
}
above programe last character will compress
if(first==next) count++
else
{
s=s.append(first).append(count);
count=1;
}
last character will not append in string buffer and
StringBuilder s=null;
it will through null pointer exceptio
public class StringCompression {
public static void main(String[] args)
{
String str="abcdd";
char first=str.charAt(0);
int count=1;
StringBuilder s=new StringBuilder();
for(int i=1;i<str.length();i++)
{
char next=str.charAt(i);
if(first==next)
count++;
else
{
s=s.append(first);
if(count>1)
s.append(count);
count=1;
}
first=next;
}
s=s.append(first);
if(count>1)
s.append(count);
System.out.println(s);
}
}
public class StringCompression {
public static void main(String[] args)
{
String str="abcdd";
char first=str.charAt(0);
int count=1;
StringBuilder s=new StringBuilder();
for(int i=1;i<str.length();i++)
{
char next=str.charAt(i);
if(first==next)
count++;
else
{
s=s.append(first);
if(count>1)
s.append(count);
count=1;
}
first=next;
}
s=s.append(first);
if(count>1)
s.append(count);
System.out.println(s);
}
}
^I think it would be infinitely more desirable if you could mention your algorithm instead of (or in addition to) posting a code. And please do follow some coding convention....you could easily have avoided so much white space from your code.
As to the question, making multiple passes through the string as mentioned in one of the previous posts would solve the problem of single character occurence.
lINKAN CHEN, If you have advice on code, please contact me by lkchen1128@gmail.com
Pass the test, but if the number of repleted charater greater than 10, if will fail
#include<iostream>
#include<string>
using namespace std;
bool
InMemoryReplace(string &ss){
int NewLength=1;
for(unsigned i=1;i<ss.length();i++){
if(ss[i-1]!=ss[i]){
NewLength++;
}
}
NewLength=NewLength*2;
if(NewLength>ss.length())
return false;
char tmp=ss[0];
int count=1;
int t=0;
for(unsigned i=1;i<=ss.length();i++){
if(tmp==ss[i]){
count++;
}
else{
ss[t]=tmp;
t++;
if(count!=1){
ss[t]=count+48;
t++;
}
tmp=ss[i];
count=1;
}
}
ss.erase(t,ss.length());
int k=1;
int m=0;
m=ss.length();
while(k<=m){
if(ss[k]>'9'||ss[k]<'0'){
ss.insert(k,1,'1');
m++;
}
k+=2;
}
return true;
}
int
main(){
string ss="abcddddddde";
InMemoryReplace(ss);
cout<<ss<<endl;
return 0;
}
Simple traverse.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void printSequence(char* array)
{
int writerPointer = 1;
int shiftCount = 0;
char sizeBuffer[10];
char ch;
ch = array[0];
int len = 0;
printf("Input : %s", array);
for(int i = 0; array[i] != '\0'; i++) {
if(ch == array[i]) {
len++;
} else {
if(len > 1) {
sprintf(array + writerPointer, "%d",len);
sprintf(sizeBuffer,"%d\0",len);
writerPointer += strlen(sizeBuffer);
} else {
shiftCount++;
}
len = 1;
array[writerPointer++] = array[i];
ch = array[i];
}
}
if(len > 1) {
sprintf(array + writerPointer, "%d",len);
sprintf(sizeBuffer,"%d\0",len);
writerPointer += strlen(sizeBuffer);
} else {
shiftCount++;
}
array[writerPointer + shiftCount] = '\0';
int hasCountFlag = 0;
for(writerPointer -= 1; writerPointer >= 0; writerPointer--) {
for(;array[writerPointer] >= '0' && array[writerPointer] <= '9'; writerPointer--) {
hasCountFlag = 1;
array[writerPointer + shiftCount] = array[writerPointer];
}
if(!hasCountFlag)
{
array[writerPointer + shiftCount] = '1';
shiftCount--;
}
array[writerPointer + shiftCount] = array[writerPointer];
hasCountFlag = 0;
}
printf("\nOutput : %s\n======================\n", array);
}
int main()
{
char buffer[1024];
strcpy(buffer,"abccccccccccccccccccccccefddddddd");
printSequence(buffer);
strcpy(buffer,"abbb");
printSequence(buffer);
strcpy(buffer,"aaab");
printSequence(buffer);
strcpy(buffer,"aaaaaaaaaaaaaaaaaaaaaaabccccccccccccccccccccccdeffffffffffffffffffffffffgh");
printSequence(buffer);
strcpy(buffer,"abcdefghhhhhhhhhhhhhhhh");
printSequence(buffer);
strcpy(buffer,"aaaaaaaaaaaaaaaaaaabccccccccccccccdefgh");
printSequence(buffer);
return 0;
}
Here is the o/p
Input : abccccccccccccccccccccccefddddddd
Output : a1b1c22e1f1d7
======================
Input : abbb
Output : a1b3
======================
Input : aaab
Output : a3b1
======================
Input : aaaaaaaaaaaaaaaaaaaaaaabccccccccccccccccccccccdeffffffffffffffffffffffffgh
Output : a23b1c22d1e1f24g1h1
======================
Input : abcdefghhhhhhhhhhhhhhhh
Output : a1b1c1d1e1f1g1h16
======================
Input : aaaaaaaaaaaaaaaaaaabccccccccccccccdefgh
Output : a19b1c14d1e1f1g1h1
======================
void compressString(char* array)
{
if(array == NULL)
return;
char c = array[0];
int length = strlen(array);
int count = 0;
int start = 0;
for(int i = 0; i < length; i++)
{
if(c == array[i])
{
count++;
}
else
{
char temp = array[i];
array[start] = c;
c = temp;
if(count == 1)
{
array[start + 1] = '1';
start+=2;
}
else
{
sprintf(&array[start + 1], "%d", count);
//increment start by one letter and one digit
start += 2;
//increment by the rest of the digits
for(float exp = 1.0; 0 <= (count - pow(10.0, exp)); exp++)
start+=1;
//reset count
count = 1;
}
}
}
array[start] = c;
sprintf(&array[start + 1], "%d", count);
}
int main()
{
char* myCharArray = new char[256];
std::cin.getline(myCharArray, 256);
compressString(myCharArray);
std::cout << myCharArray << std::endl;
delete [] myCharArray;
return 0;
}
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
char str[1000];
int l ,i;
int ct , prev , ans;
scanf("%s",str);
l = strlen(str);
ct = 1 ;
prev = 0;
ans = 1 ;
while(1)
{
if(str[ct] == str[prev])
ans++;
else
{
printf("%c%d",str[prev],ans);
prev = ct;
ans = 1;
}
ct++;
if(ct == l)
break;
}
printf("%c%d",str[prev],ans);
printf("\n");
return 0;
}
Use HashMap
Key - Character
value - No of times its getting repeated.
Later, Prepare a string with key+value pairs of HashMap.
Note: When you scan to next character , You should always delete the entry in the hashmap for previous key .
I think this works pretty good and simple.
ANy comments ???
#include<stdio.h>
#include<conio.h>
void compress(char str[])
{
int i=0;
char ch=str[i];
int k=0;
//printf("%s",str);
while(str[i])
{
// printf("\nentered while %d",i);
if(ch == str[i])
{
k++;
}
else
{
printf("%c%d",str[i-1],k);
k=1;
ch=str[i];
}
i++;
}
printf("%c%d",str[i-1],k);
}
int main()
{
char str[100];
printf("Enter the string");
gets(str);
compress(str);
getch();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
char *compressStr(char *str)
{
int len, charCount, newStrIdx, i;
char *newStr, *originalStr;
char prevChar;
char itoaBuffer[32];
assert(str);
len = strlen(str);
newStr = (char *)malloc(len+1);
assert(newStr);
memset(newStr, '\0', sizeof(newStr));
charCount = 0;
newStrIdx = 0;
prevChar = '\0';
for (i=0; i <= len; ++i) {
if (str[i] == prevChar) {
++charCount;
}
else
{
if (charCount > 1) {
sprintf(itoaBuffer, "%d", charCount);
strcpy(&newStr[newStrIdx], &itoaBuffer[0]);
newStrIdx++;
}
newStr[newStrIdx] = str[i];
++newStrIdx;
charCount = 1;
}
prevChar = str[i];
}
if (strlen(newStr) >= len)
{
originalStr = (char *)malloc(len+1);
assert(originalStr);
strcpy(originalStr, str);
return originalStr;
}
return newStr;
}
int main(int argc, char *argv[])
{
if (argc <= 1)
{
fprintf(stderr, "Please specify a string to compress\n");
return -1;
}
//char stringToCompress[] = "aabcccccaaad";
char *stringToCompress = argv[1];
char *compressedString;
printf("Original string is %s, len = %d\n", stringToCompress, strlen(stringToCompress));
compressedString = compressStr(stringToCompress);
printf("Compressed string is %s, len = %d\n", compressedString, strlen(compressedString));
free(compressedString);
return 0;
}
public class StringCompress {
public static void main(String[] args) {
StringBuffer str= new StringBuffer("aaaabbbbbccchhh");
int count=1;
char prev= str.charAt(0);
for(int i=1;i<str.length();)
{
if(prev==str.charAt(i))
{
str.deleteCharAt(i);
count++;
}
else
{
str.insert(i,count);
prev=str.charAt(i+1);
count=1;
i=i+2;
}
}
str.insert(str.length(),count);
System.out.println(str);
}
static char[] compressedString(char[] array)
{
int globalIndex = 0;
for (int i = 0; i < array.length; ) {
char current = array[i];
int count = 1;
int j = i + 1;
for (; j < array.length && current == array[j] ; j++) {
count++;
}
array[globalIndex++] = current;
char[] countDigitArray = ("" + count).toCharArray();
if (count >1 ) {
for (int k = 0; k < countDigitArray.length; k++)
array[globalIndex++] = countDigitArray[k];
}
i = j;
}
int singleCount = 0;
for (int i = 1; i < globalIndex;i++ ) {
if ((array[i] < 48 || array[i] > 57) && (array[i - 1] < 48 || array[i - 1] > 57)) {
singleCount++;
}
}
if (globalIndex + singleCount > array.length) {
throw new IllegalArgumentException("You do not have sufficent array sice for this manipulation.");
}
int endIndex = globalIndex + singleCount - 1;
int lastIndex = globalIndex - 1;
for (int i = endIndex ; i > 0 && singleCount > 0; i--) {
array[i] = array[lastIndex--];
if ((array[i] < 48 || array[i] > 57) && (array[lastIndex] < 48 || array[lastIndex] > 57)) {
array[i - 1] = '1';
i--;
singleCount--;
}
}
for (int i = endIndex + 1; i < array.length; i++) {
array[i] = ' ';
}
return array;
}
O(n)
public static String compress(String str){
if(str.length()<=1)
return str;
int current=0;
int next=current+1;
char curch=str.charAt(current);
StringBuilder sb=new StringBuilder();
sb.append(curch);
int count=1;
while(next<=str.length()-1){
if(str.charAt(current)==str.charAt(next)){
count++;
}
else
{
sb.append(count);
sb.append(str.charAt(next));
count=1;
}
current++;
next++;
if(next>=str.length()){
sb.append(count);
break;
}
}
if(str.length()<sb.length())
return str;
else
return sb.toString();
}
}
public static void main(String[] args){
String s = "abbbccaaa";
char[] orig = s.toCharArray();
char[] compress = new char[orig.length];
int count = 0;
int index = 0;
int compIn = 0;
while(index < orig.length){
if(compIn - 1 >= 0){
if(compress[compIn - 1] != orig[index]){
if(compress[compIn] == '\u0000'){
compress[compIn] = Character.forDigit(count, 10);
count = 1;
compIn++;
}
compress[compIn] = orig[index];
count = 1;
compIn++;
}else{
count++;
}
}else{
compress[compIn] = orig[index];
count++;
compIn++;
}
index++;
}
if(compIn < orig.length)
compress[compIn] = Character.forDigit(count, 10);
if(compIn == orig.length){
System.out.println("hello");
System.out.println(orig);
}
else{
System.out.println(compress);
}
}
String MyString = "AADDBBBBCEEEAAAAARR";
StringBuilder result =new StringBuilder();
int count =1;
int i;
for(i=0;i< MyString.length()-1;i++){
if(MyString.charAt(i)==MyString.charAt(i+1)){
count++;
}
else{
result.append(MyString.charAt(i));
if(count>1)
result.append(count);
count=1;
}
}
result.append(MyString.charAt(i));
if(count>1)
result.append(count);
System.out.println("resultString"+ "-->" + result);
String MyString = "AADDBBBBCEEEAAAAARR";
StringBuilder result =new StringBuilder();
int count =1;
int i;
for(i=0;i< MyString.length()-1;i++){
if(MyString.charAt(i)==MyString.charAt(i+1)){
count++;
}
else{
result.append(MyString.charAt(i));
if(count>1)
result.append(count);
count=1;
}
}
result.append(MyString.charAt(i));
if(count>1)
result.append(count);
System.out.println("resultString"+ "-->" + result);
LinkedHashMap<Character, Integer> charCount = new LinkedHashMap<Character,Integer>();
for(int i=0; i<input.length(); i++){
Character c = input.charAt(i);
if(charCount.containsKey(c)){
charCount.put(c, charCount.get(c)+1);
}
else{
charCount.put(c, 1);
}
}
StringBuilder sb = new StringBuilder();
for(Character c: charCount.keySet()){
sb.append(c);
sb.append(charCount.get(c));
}
return sb.toString();
/**
* @param {character[]} chars
* @return {number}
*/
function stringCompression(chars) {
let output = "";
let count = 0;
for (let i = 0; i < chars.length; i++) {
let current = chars[i];
let next = chars[i+1];
// if current == next
count++;
if (current != next) {
output += current + count;
count = 0;
}
}
chars = output.split("");
console.log(chars);
return chars.length;
};
public static String stringCompressor(String str) {
if (str==null || str.isEmpty() ) return "empty string";
else {
StringBuffer compressed = new StringBuffer();
char last = str.charAt(0);
int count=1;
for (int c=1; c<str.length(); c++) {
if(str.charAt(c) == last) {
count++;
} else {
compressed.append(last+""+count);
last = str.charAt(c);
System.out.println(last);
count=1;
}
}
compressed.append(last+""+count);
if (str.length() <= compressed.length()) return str;
else return compressed.toString();
}
}
#include<iostream>
#include<string>
using namespace std;
int main()
{
bool flag=false;
char str1[200];
char str2[200]={0};
int len;
int j=0;
int k=1;
cout<<"Enter the string\n";
gets(str1);
len=strlen(str1);
for(int i=0;i<len;i++)
{
if(str1[i]==str1[i+1])
{
k++;
continue;
}
else
{
flag=true;
}
if(flag)
{
str2[j++]=str1[i];
if(k>=10)
{
str2[j++]=k/10+48;
str2[j++]=k%10+48;
}
else
{
str2[j++]=k+48;
}
k=1;
flag=false;
}
}
cout<<str2;
getchar();
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int main()
{
bool flag=false;
char str1[200];
char str2[200]={0};
int len;
int j=0;
int k=1;
cout<<"Enter the string\n";
gets(str1);
len=strlen(str1);
for(int i=0;i<len;i++)
{
if(str1[i]==str1[i+1])
{
k++;
continue;
}
else
{
flag=true;
}
if(flag)
{
str2[j++]=str1[i];
if(k>=10)
{
str2[j++]=k/10+48;
str2[j++]=k%10+48;
}
else
{
str2[j++]=k+48;
}
k=1;
flag=false;
}
}
cout<<str2;
getchar();
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int main()
{
bool flag=false;
char str1[200];
char str2[200]={0};
int len;
int j=0;
int k=1;
cout<<"Enter the string\n";
gets(str1);
len=strlen(str1);
for(int i=0;i<len;i++)
{
if(str1[i]==str1[i+1])
{
k++;
continue;
}
else
{
flag=true;
}
if(flag)
{
str2[j++]=str1[i];
if(k>=10)
{
str2[j++]=k/10+48;
str2[j++]=k%10+48;
}
else
{
str2[j++]=k+48;
}
k=1;
flag=false;
}
}
cout<<str2;
getchar();
return 0;
}
Do check my code. I have used recurssion to solve it in c++. Let me know if it fails any testcase:
string CombineWithNoExtraSpace(string S)
{
int n=S.size(),count=1,i=0;
if(i==n) return "\0";
while(i+1<=n && S[i]==S[i+1] )
{
count++;
i++;
}
S = S[i] + to_string(count) + combine(S.substr(i+1,n-count));
return S;
}
I did not perform any validation on input. This is solution for compression
public class StringCompress
{
public static void main(String[] args)
{
String s = "aaabbcccddee";
System.out.println(compress(s));
}
static String compress(String s) {
int i = 0, j = 0;
char ch = s.charAt(i++);
while(i < s.length()) {
if(ch != s.charAt(i)) {
int count = i-j;
s = s.substring(0, j+1) + count + s.substring(i, s.length());
ch = s.charAt(i);
i = j + 2;
j = i;
}
i++;
}
int count = i-j;
s = s.substring(0, j+1) + count + s.substring(i, s.length());
return s;
}
}
def self.compress(string)
return "" if string.empty?
result = ""
current = string[0]
count = 1
string.split(//).inject({result:"", last: "", count:0}) do |acum, c|
if c != last && !last.empty?
acum[:result] += "#{acum[:last]}#{acum[:count]}"
acum[:count] = 1
acum[:last] = c
end
(1..(string.size)).each do |index|
if (current == string[index])
count += 1
else
result = result + "#{current}#{count}"
count = 1
current = string[index]
end
end
result
end
def self.compress(string)
return "" if string.empty?
result = ""
current = string[0]
count = 1
string.split(//).inject({result:"", last: "", count:0}) do |acum, c|
if c != last && !last.empty?
acum[:result] += "#{acum[:last]}#{acum[:count]}"
acum[:count] = 1
acum[:last] = c
end
(1..(string.size)).each do |index|
if (current == string[index])
count += 1
else
result = result + "#{current}#{count}"
count = 1
current = string[index]
end
end
result
end
StringBuilder compressString(String s)
{
c=s.toCharArray();
int count=1;
char last=c[0];
StringBuilder compress=new StringBuilder();
for(int i=1;i<c.length;i++)
{
if( c[i]==last)
{
count++;
}
else
{
compress.append(""+last+count);
count=1;
}
last=c[i];
}
compress.append(""+last+count);
return compress;
}
public static String compress(String input) {
if ((input == null) || input.isEmpty()) {
return "";
}
int count = 1;
String result = "";
char prevChar = input.charAt(0);
for (int i = 1; i < input.length(); i++) {
char thisChar = input.charAt(i);
if (thisChar == prevChar) {
count++;
} else {
result += prevChar + "" + count;
count = 1;
prevChar = thisChar;
}
}
result += prevChar + "" + count;
return result;
}
O(n) time complexity solution..
Here is my Java solution:
public static String compress(String s) {
if(s==null||s.length()<2) {
throw new IllegalArgumentException();
}
StringBuilder sb = new StringBuilder(s);
int sIndex = 0;
int currCnt=1;
char currChar = sb.charAt(0);
char nextChar;
for(int i=1;i<sb.length();i++) {
nextChar = sb.charAt(i);
if(nextChar==currChar) {
currCnt++;
}else {
sb.setCharAt(sIndex++, currChar);
sb.setCharAt(sIndex++, (""+currCnt).charAt(0));
currChar = nextChar;
currCnt=1;
}
}
sb.setCharAt(sIndex++, currChar);
sb.setCharAt(sIndex++, (""+currCnt).charAt(0));
sb.setLength(sIndex);
return sb.toString();
}
public static String unCompress(String s) {
HashMap<Character, Integer> m1 = new LinkedHashMap<Character, Integer>();
StringBuilder get = new StringBuilder();
char[] c = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (m1.containsKey(c[i])) {
m1.put(c[i], m1.get(c[i]) + 1);
} else {
m1.put(c[i], 1);
}
}
for (Entry<Character, Integer> entryset : m1.entrySet()) {
// System.out.println(entryset.getKey()+entryset.getValue());
get.append(entryset.getKey()).append(entryset.getValue());
}
return get.toString();
}
public static String unCompress(String s) {
HashMap<Character, Integer> m1 = new LinkedHashMap<Character, Integer>();
StringBuilder get = new StringBuilder();
char[] c = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (m1.containsKey(c[i])) {
m1.put(c[i], m1.get(c[i]) + 1);
} else {
m1.put(c[i], 1);
}
}
for (Entry<Character, Integer> entryset : m1.entrySet()) {
// System.out.println(entryset.getKey()+entryset.getValue());
get.append(entryset.getKey()).append(entryset.getValue());
}
return get.toString();
}
public static String unCompress(String s) {
HashMap<Character, Integer> m1 = new LinkedHashMap<Character, Integer>();
StringBuilder get = new StringBuilder();
char[] c = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (m1.containsKey(c[i])) {
m1.put(c[i], m1.get(c[i]) + 1);
} else {
m1.put(c[i], 1);
}
}
for (Entry<Character, Integer> entryset : m1.entrySet()) {
// System.out.println(entryset.getKey()+entryset.getValue());
get.append(entryset.getKey()).append(entryset.getValue());
}
return get.toString();
}
}
public static String unCompress(String s) {
HashMap<Character, Integer> m1 = new LinkedHashMap<Character, Integer>();
StringBuilder get = new StringBuilder();
char[] c = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (m1.containsKey(c[i])) {
m1.put(c[i], m1.get(c[i]) + 1);
} else {
m1.put(c[i], 1);
}
}
for (Entry<Character, Integer> entryset : m1.entrySet()) {
// System.out.println(entryset.getKey()+entryset.getValue());
get.append(entryset.getKey()).append(entryset.getValue());
}
return get.toString();
}
}
String compressStr(String inputString)
{
String compressedString ="";
int i=0;
int j=i+1;
char[] chars = inputString.toCharArray();
while(i< chars.length)
{
int counter=1;
compressedString = compressedString + chars[i];
while(j<chars.length && chars[j] == chars[i]) {
i++;
j++;
counter++;
}
compressedString = compressedString + counter;
i++;
j++;
}
return compressedString;
}
String compressStr(String inputString)
{
String compressedString ="";
int i=0;
int j=i+1;
char[] chars = inputString.toCharArray();
while(i< chars.length)
{
int counter=1;
compressedString = compressedString + chars[i];
while(j<chars.length && chars[j] == chars[i]) {
i++;
j++;
counter++;
}
compressedString = compressedString + counter;
i++;
j++;
}
return compressedString;
}
Java Solution:-
package test;
import java.util.*;
public class test {
public static void main (String[] args)
{
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int prev_char_idx = 0, curr_char_idx = 0;
if(s.length() > 0) {
do {
if (s.charAt(prev_char_idx) != s.charAt(curr_char_idx)) {
int count = curr_char_idx - prev_char_idx;
int calc_digit = calc(count);
char c = s.charAt(prev_char_idx);
s = s.substring(0, prev_char_idx) + s.charAt(prev_char_idx)
+ (count) + s.substring(curr_char_idx, s.length());
prev_char_idx += calc_digit + 1;
curr_char_idx = prev_char_idx - 1;
}
curr_char_idx++;
} while (curr_char_idx < s.length());
// calculate for the last
int count = curr_char_idx - prev_char_idx;
s = s.substring(0, prev_char_idx) + s.charAt(prev_char_idx)
+ (count) + s.substring(curr_char_idx, s.length());
}
System.out.println(s);
sc.close();
}
private static int calc(int count) {
int n = 0;
while (count > 0) {
count /= 10;
n++;
}
return n;
}
}
private static String compress(String input) throws Exception {
List<Pair> occurrence = new ArrayList<>();
Arrays.stream(input.split("")).forEach(character -> {
if (!occurrence.isEmpty() && occurrence.get(occurrence.size() - 1).equals(new Pair(character, 1))) {
occurrence.get(occurrence.size() - 1).updateOccurrence();
} else {
occurrence.add(new Pair(character, 1));
}
});
String squeezedString = occurrence.stream().map(Pair::toString).collect(Collectors.joining());
if (squeezedString.length() <= input.length())
return squeezedString;
throw new Exception("Buffer overflow");
}
private static class Pair {
private final String character;
private int occurrence;
Pair(String character, int occurrence) {
this.character = character;
this.occurrence = occurrence;
}
String getCharacter() {
return character;
}
void updateOccurrence() {
occurrence = ++occurrence;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Pair)) return false;
Pair pair = (Pair) o;
return getCharacter().equals(pair.getCharacter());
}
@Override
public int hashCode() {
return Objects.hash(getCharacter());
}
@Override
public String toString() {
return String.format("%s%s", character, occurrence);
}
}
public static void compressCharArray() {
char[] array = "aabccccdghhhhhhh".toCharArray();
for(int i = array.length - 1; i >= 1; i--) {
int count = 1;
while(i >= 1 && array[i] == array[i-1]) {
count++;
array[i] = 0;
i--;
}
if(count > 1 && i >= 0) {
array[i+1] = (char)(48+count);
}
}
for (int i = 0; i < array.length; i++) {
int holeStartIndex = i;
while(i < array.length && array[i] == 0) i++;
for(int j = i; j < array.length - (j - holeStartIndex); j++,holeStartIndex++) array[holeStartIndex] = array[j];
}
System.out.println(Arrays.toString(array));
}
String str = "aabbccddee";
char currentChar = str.charAt(0);
int count = 1;
String charCount ="";
for ( int i =1 ; i<str.length(); i++){
if(currentChar==str.charAt(i)){
count++;
}else{
charCount = charCount+ currentChar+""+count;
count =1;
currentChar = str.charAt(i);
}
}
charCount = charCount+currentChar+""+count;
System.out.println(charCount);
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *tmp = NULL;
void *duplicate_str(char *a) {
tmp = (char *)malloc(256);
memset(tmp, 0, 256);
int count[256] = {0};
int i = 0, j = 0;
char st[100] = {0};
while(a[i]) {
++count[a[i]];
/*--------------------------------------------------------*/
/*--- Handeling for duplicate characters count and ------*/
/*--- assign new character post duplicate characters ---*/
/*-------------------------------------------------------*/
if(a[i] != a[i-1]) {
if(i==0) {
tmp[j] = a[i];
}
else {
if(count[a[i-1]] > 1) {
sprintf(st, "%d", count[a[i-1]]);
tmp[j] = st[0];
tmp[++j] = a[i];
}
else {
tmp[j] = a[i];
}
count[a[i-1]] = 0;
}
j++;
}
else {
if(count[a[i]] == 1) {
tmp[j] = a[i];
++j;
}
}
i++;
}
/*------------------------------------*/
/*--- Handeling for last character ---*/
/*------------------------------------*/
sprintf(st, "%d", count[a[i-1]]);
tmp[j] = st[0];
/*------------------------------------*/
memset(a, 0, strlen(a));
strncpy(a, tmp, strlen(tmp));
free(tmp);
tmp = NULL;
}
int main()
{
char *a = NULL;
a = (char *)malloc(sizeof("wwwwaaadexxxxxxywww"));
memset(a, 0, sizeof("wwwwaaadexxxxxxywww"));
strncpy(a, "wwwwaaadexxxxxxywww", sizeof("wwwwaaadexxxxxxywww"));
printf("Input String: %s\n", a);
duplicate_str(a);
printf("Output String: %s\n", a);
free(a);
a = NULL;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *tmp = NULL;
void *duplicate_str(char *a) {
tmp = (char *)malloc(256);
memset(tmp, 0, 256);
int count[256] = {0};
int i = 0, j = 0;
char st[100] = {0};
while(a[i]) {
++count[a[i]];
/*--------------------------------------------------------*/
/*--- Handeling for duplicate characters count and ------*/
/*--- assign new character post duplicate characters ---*/
/*-------------------------------------------------------*/
if(a[i] != a[i-1]) {
if(i==0) {
tmp[j] = a[i];
}
else {
if(count[a[i-1]] > 1) {
sprintf(st, "%d", count[a[i-1]]);
tmp[j] = st[0];
tmp[++j] = a[i];
}
else {
tmp[j] = a[i];
}
count[a[i-1]] = 0;
}
j++;
}
else {
if(count[a[i]] == 1) {
tmp[j] = a[i];
++j;
}
}
i++;
}
/*------------------------------------*/
/*--- Handeling for last character ---*/
/*------------------------------------*/
sprintf(st, "%d", count[a[i-1]]);
tmp[j] = st[0];
/*------------------------------------*/
memset(a, 0, strlen(a));
strncpy(a, tmp, strlen(tmp));
free(tmp);
tmp = NULL;
}
int main()
{
char *a = NULL;
a = (char *)malloc(sizeof("aabbccc"));
memset(a, 0, sizeof("aabbccc"));
strncpy(a, "aabbccc", sizeof("aabbccc"));
printf("Input String: %s\n", a);
duplicate_str(a);
printf("Output String: %s\n", a);
free(a);
a = NULL;
}
or way less lines:
public String compress(String s) {
String out = "";
int sum = 1;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) == s.charAt(i+1)) {
sum++;
} else {
out = out + s.charAt(i) + sum;
sum = 1;
}
}
out = out + s.charAt(s.length() - 1) + sum;
return out.length() < s.length() ? out : s;
}
<pre lang="c" line="1" title="CodeMonkey39938" class="run-this">#include<stdio.h>
#include<conio.h>
void main(){
char str[20];
int i,k=1,m=1;
clrscr();
printf("Enter The String");
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
if(str[i]!=str[i+1])
k++;
i--;k--;
k=k*2;
if(i<k)
printf("Invalid input try again");
else{
for(i=0;str[i]!='\0';i++)
if(str[i]==str[i+1])
m++;
else{
printf("%c",str[i]);
printf("%d",m);
m=1;
}
}
getch();
}</pre>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,count[20],i,j;
char a[200];
gets(a);
n=strlen(a);
for(i=0;i<n;i++)
{
count[i]=1;
}
i=0;
j=0;
while(i<n&&j<n)
{
if(a[i]==a[i+1])
{
i++;
count[j]++;
continue;
}
else
{
cout<<a[j];
if(count[j]>1)
cout<<count[j];
i++;
j=i;
continue;
}
}
return 0;
}
Take two temp char variable prev & next. Initialize them to 0th & 1st element in array.
also take one more int variable prev_idx to keep track of previous char on which we are iterating. initialize prev_idx to 0.
Keep iterating on array. If prev & next are equal increment the count variable.
Otherwise set element at prev_idx+1 to char value of count && prev_idx +2 next && set count to 1 && increment prev_idx twice.
Check my solution:
- Anonymous January 22, 2011static string CompressString(string str) { if (str == null) { throw new ArgumentNullException("str"); } if (str.Length < 2) { return str; } var chars = str.ToCharArray(); int insertIndex = 0; int i = 0; while (i < chars.Length) { int j = i + 1; int counter = 1; while (j < chars.Length && chars[j] == chars[i]) { i++; j++; counter++; } chars[insertIndex] = chars[i]; if (counter > 1) { var countAsString = counter.ToString(); foreach (var theChar in countAsString) { chars[++insertIndex] = theChar; } } insertIndex++; i = j; } return new string(chars, 0, insertIndex); }