String Compression III | Simple Simulation | Leetcode 3163 | codestorywithMIK

This is the 48th Video of our Playlist "Binary Tree : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve an easy string Problem : String Compression III | Simple Simulation | Leetcode 3163 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : String Compression III | Simple Simulation | Leetcode 3163 | codestorywithMIK
Company Tags : will update later

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
Initialization: Start with an empty StringBuilder to construct the compressed string and use an index i to traverse the input string.
Traverse the String: Iterate through the string character by character.
Count the number of consecutive occurrences of the current character (up to a maximum of 9).
Update the Result: Append the count followed by the character to the StringBuilder.
Move Forward: Increment i to move to the next group of characters and repeat until the end of the string.
Return: Convert the StringBuilder to a String and return the compressed result.

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[gauravmundhada]

Solved on my own. Here to learn something new and support MIK.

[RishabhJain-uhbt]

Wo chota sa motivation wala section wapas le aao😅

[amanpaliwalvlogs]

Come for greeting...

Radhe radhe radhe radhe radhe

[madhumithaakula]

class Solution {
public:
string compressedString(string word) {
int n=word.length();
string comp="";
int freq=1;
for(int i=0;i<n;i++){
if(word[i]==word[i+1]){
freq++;
if(freq>9){
comp.push_back('9');
comp.push_back(word[i-1]);
freq=1;
}

}
else{
comp.push_back('0' + freq);
comp.push_back(word[i]);
freq=1;
}

}

return comp;
}
}; //thanks anna because of your videos now i'm able to doing it own now

[im_ykp]

Came across a similar question asked in Microsoft OA. The question was to minimize the length of the compressed string by removing exactly K consecutive elements. We have to report the minimum length of the compressed string.
Can you make a video on it??

[riteshtiwari]

I am remind u all that this question is from May 24 contest weekly. I had solved it that time and it reminds me 😅

[HARSHRAJ-wzrp]

class Solution {
public:
string compressedString(string word) {
int p;
vector<char> alpha;
vector<int> harsh;
char ch=word[0];
int count=0;
for(int i=0;i<word.size();i++){
if(word[i]==ch){
count++;
}else{
harsh.push_back(count);
alpha.push_back(ch);
ch=word[i];
count=1;
}
}
harsh.push_back(count);
alpha.push_back(ch);
string output="";
int q;
for(int i=0;i<harsh.size();i++){
p=harsh[i]/9;
if(p!=0){
for(int j=1;j<=p;j++){
output+='9';
output+=alpha[i];
}
q=harsh[i]%9;
if(q!=0){
output+=q+'0';
output+=alpha[i];
}
}else{
q=harsh[i]%9;
output+=q+'0';
output+=alpha[i];
}
}
return output;
}
};

[ShashankShekharShukla-xwrc]

Soory FOR LATE HERE MY SIMPLE COUNTING AND LOOKING APPROCH
TIME COMPLEXITY => O(N)
SPACE COMPLEXITY =O(1) Ignore extra string (AS WE HAVE TO RETURN ONLY STRING IN OUTPUT)
CODE :
string compressedString(string &word)
{
int cnt = 1;
string ans = "";
if (word.size() == 1)
{
ans += to_string(cnt);
ans += word[0];
}
else
{
for (int i = 0; i < word.size(); i++)
{
if (i == word.size() - 1)
{
if (ans.back() == word[i])
{
cnt += 1;
ans += to_string(cnt);
ans += word[i];
}
else
{
cnt = 1;
ans += to_string(cnt);
ans += word[i];
}
}
else if (word[i] != word[i + 1])
{
cnt = 1;
ans += to_string(cnt);
ans += word[i];
}
else if (word[i] == word[i + 1])
{
while (i < word.size() - 1 && word[i] == word[i + 1])
{
cnt += 1;
i++;
}
if (cnt > 9)
{
while (cnt > 9)
{
ans += to_string(9);
ans += word[i];
cnt = cnt - 9;
}
}
ans += to_string(cnt);
ans += word[i];
cnt = 1; // reset count
}
}
}
return ans;
}

[arnabsarkar]

My Little Complex Solution 💀

// TC : O(n) + O(m * 1111)

public String myApproach(String word) {
int n = word.length(), count = 1, num = 0;
StringBuilder sb = new StringBuilder();
StringBuilder ans = new StringBuilder();

// TC : O(n)
for (int i = 1; i < n; i++) {
char c1 = word.charAt(i - 1), c2 = word.charAt(i);

if (c2 == c1) {
count++;
}
else {
sb.append(count);
sb.append(c1);
count = 1;
}
}

sb.append(count);
sb.append(word.charAt(n - 1));

/*

TC : O(m * assuming a single char has been repeated for
10^5 times. So in that case value of times will be 1111.11

*/
for (int i = 0; i < sb.length(); i++) {
char ch = sb.charAt(i);
int x = (int)(ch);

if (x >= 48 && x <= 57) {
num = num * 10 + (ch - '0');
}
else {
int times = num / 9, remaning = num % 9;

for (int k = 1; k <= times; k++) {
ans.append('9');
ans.append(ch);
}

if (remaning > 0) {
ans.append(remaning);
ans.append(ch);
}

num = 0;
}
}

return ans.toString();
}

[Playvish]

solved it easily

class Solution {
public:
string compressedString(string word) {
string ans = "";
int cnt = 1;

int i = 1;
int size = word.length();

while(i<size){
if(word[i]==word[i-1]){
if(cnt<9){
cnt++;
}else{
ans += (48 + cnt); //44 = ascii of 0
ans += word[i];
cnt = 1;
}

}else{
ans += (48 + cnt);
cnt = 1;
ans += word[i-1];
}
i++;
}

ans += to_string(cnt);
ans += word[i-1];

return ans;
}
};

[salmaniproductions]

Solved by own, Thank you bhaiyya <3

Here is my Solution -

class Solution {
public:
string compressedString(string word) {
int count=1;
string comp ="";

for(int i=0;i<word.length();i++){
if(count>9){
comp.push_back('9');
comp.push_back(word[i]);
count=1;
}

if(word[i]==word[i+1] and i+1<word.length()){
count++;
}
else if (word[i]!=word[i+1] ){
comp.push_back(count+'0');
comp.push_back(word[i]);
count=1;
}
}

return comp;
}
};

[jeehub]

Done Without 2 While loops but same time complexity😇😅

string compressedString(string word) {
char ch=word[0];
int cnt=1;
string ans="";
for(int i=1; i<word.size(); i++)
{
if(word[i]==ch)
{
cnt++;
if(cnt>9)
{
ans+=to_string(9)+ch;
cnt-=9;
}

}

else
{
ans+=to_string(cnt)+ch;
ch=word[i];
cnt=1;

}
}
ans+=to_string(cnt)+ch;
return ans;
}

[aizadiqbal]

i tried first with freq array, got the order issue
then tried linkedhashmap, got the issue of same char present at diff locations...
then i thought of an approach similar to yours, counting the individual freq, but didn't feel like coding it...I will code that way too now...

[AryanVats]

my approach sir

string compressedString(string s) {
int n=s.length();
int count=1;
string comp="";

for(int i=0;i<n-1;i++){
if(s[i+1]==s[i] && count<9){
count++;
}
else{
comp+=to_string(count)+s[i];
count=1;
}
}

return comp;
}

[ReshuSharma-jcyu]

MIK bhaiya can i use hashmap in this problem

[SRoy]

my approach :
string compressedString(string word) {
int i=0;
int count=0;
string ans="";
int n = word.size();
int j=0;
for(;j<n;j++){
if(word[i] == word[j] && j-i+1 <=9){
count++;
}else if(word[i] != word[j] || j-i+1>9){

i=j;
count=1;
}
}



return ans;
}

[sahebraojadhav]

Bhayya can u please upload solution of yesterdays contest hard problem

[Abhishek]

class Solution {
public:
string compressedString(string word) {
int n = word.size();
string comp = "";
for(int i = 0; i < n; i++)
{
long long freq = 1;
while(i < n && word[i] == word[i + 1])
{
freq++;
i++;
}
while(freq > 9)
{
comp += to_string(9) + word[i];
freq -= 9;
}
if(freq > 0) comp += to_string(freq) + word[i];
}
return comp;
}
};

[pradyumnmulegaon]

My c++ solution:
class Solution {
public:
string compressedString(string word) {
int i = 0;
int n = word.length();
int count = 0;
string comp;
while(i < n){
char ch = word[i];

while(i<n && word[i] == ch){
i++;
count++;
}

if(count <= 9){
comp.push_back((count) + '0');
comp.push_back(ch);
}else{
while(count > 9){
comp.push_back('9');
comp.push_back(ch);
count -= 9;
}
comp.push_back(count + '0');
comp.push_back(ch);

}

count = 0;
}

return comp;
}
};

[asutoshbikun]

Bhai Leetcode ke contest problems bhi karo pls...