Blogs Hub

String Compression - MiniTV

String Compression - मिनी टीवी

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

 

Follow up:

Could you solve it using only O(1) extra space?

 

Example 1:

Input:

["a","a","b","b","c","c","c"]

Output:

Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:

"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

 

Example 2:

Input:

["a"]

Output:

Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:

Nothing is replaced.

 

Example 3:

Input:

["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:

Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:

Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".

Notice each digit has its own entry in the array.

 

Note:

All characters have an ASCII value in [35, 126].

1 <= len(chars) <= 1000.

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
    public class CompressSoln
    {
        public int Compress(char[] chars)
        {
            if (chars==null)
                return 0;
            if (chars.Length == 1)
                return 1;

            int slow = 0;
            int fast = 1;
            int index = 0;
            while(fast <= chars.Length)
            {
                if ( fast < chars.Length && chars[slow] == chars[fast])
                {
                    fast++;
                }
                else if(fast == chars.Length)
                {
                    slow = UpdateSlowFastPointer(chars, slow, fast,ref index);
                    break;
                }
                else
                {
                    slow = UpdateSlowFastPointer(chars, slow, fast,ref index);
                }                
            }

            return index;
        }

        private static int UpdateSlowFastPointer(char[] chars, int slow, int fast,ref int index)
        {
            if (fast - slow == 1)
            {
                chars[index] = chars[slow];
                if (chars.Length != fast)
                {
                    slow++;
                }                
            }
            else
            {
                int diff = fast - slow;
                var charArr = diff.ToString().ToCharArray();
                chars[index] = chars[slow];
                foreach (var item in charArr)
                {                    
                    index++;
                    chars[index] = item;                    
                }
                slow=fast;                
            }
            index++;

            return slow;
        }
    }
}

 

Time Complexity: O(n)

Space Complexity: O(1)

 

Test Cases:

using LeetCode.AskGif.Easy.String;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.String
{
    [TestClass]
    public class CompressSolnTests
    {
        [TestMethod]
        public void RepeatedSubstringPatternSoln_First()
        {
            var input = new char[] { 'a', 'a', 'b', 'b', 'c', 'c', 'c' };
            var output = 6;
            var res = new CompressSoln().Compress(input);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void RepeatedSubstringPatternSoln_Second()
        {
            var input = new char[] { 'a' };
            var output = 1;
            var res = new CompressSoln().Compress(input);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void RepeatedSubstringPatternSoln_Third()
        {
            var input = new char[] { 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b' };
            var output = 4;
            var res = new CompressSoln().Compress(input);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void RepeatedSubstringPatternSoln_Fourth()
        {
            var input = new char[] {'a', 'a', 'a', 'b', 'b', 'a', 'a'};
            var output = 6;
            var res = new CompressSoln().Compress(input);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void RepeatedSubstringPatternSoln_Fifth()
        {
            var input = new char[]{'a', 'a', 'a', 'a', 'a', 'b'};
            var output = 3;
            var res = new CompressSoln().Compress(input);

            Assert.AreEqual(res, output);
        }

        [TestMethod]
        public void RepeatedSubstringPatternSoln_Sixth()
        {
            var input = new char[] {'a', 'a', 'a', 'a', 'b', 'a'};
            var output = 4;
            var res = new CompressSoln().Compress(input);

            Assert.AreEqual(res, output);
        }
    }
}