Remove Consecutive Characters | InterviewBit | Solution Explained

InterviewBit Remove Consecutive Characters. Solution explained simply & in detail. Problem Link

0. Remove Consecutive Characters: Problem Discussion

0.0. IO Format

  • Given: String s and integer k
  • Goal: Return another string ns
  • Condition: remove all k consecutive characters in s

0.1. Examples

  • s = “aabcd”, k = 2 → “bcd”
  • s = “aabbcccd”, k = 2 → “cd”

1. Remove Consecutive Characters: Observations & Logic

1.0. Intuitions

How do we start to think about this problem? Since the question mentions “consecutive characters”, we can start with that.

1.1. Consecutive Characters

The first goal is to identify and extract all the consecutive character sequences.

Since there could be many, we can store them in a list. This is how it looks:

 Remove Consecutive Characters: test case for string "aaabaaccc"
Remove Consecutive Characters: test case for string “aaabaaccc”

1.2. Removing Consecutive Characters

Now we have to remove a sequence of k consecutive characters. Let’s say that k = 2 in our case. What will happen?

 Remove Consecutive Characters: test case for k = 2
Remove Consecutive Characters: test case for k = 2

What if k = 3?

Remove Consecutive Characters: test case for k = 3
Remove Consecutive Characters: test case for k = 3

By now, we realize that the answer is simply taking the len(consecutive_characters) % k as the final length!

2. Remove Consecutive Characters: Optimized Implementation

2.0. Code

class Solution:
    def solve(self, s, k):
        i = 0
        a = []
        while i < len(s):
            a.append(s[i])
            while i+1 < len(s) and s[i] == s[i+1]:
                a[-1] += s[i]
                i += 1
            i += 1

        ns = ""
        for ccs in a:
            final_len = len(ccs)%k
            ns += ccs[0]*final_len
        
        return ns

2.1. Complexity Analysis

Where N = len(s)

  • Time: O(N) to iterate over all the characters in s once and then to iterate over all the strings in a. Both are of len = N.
  • Space: O(N) to store the consecutive characters string.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

      A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

      Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

      To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

      Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

      This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

      Understanding why solar energy consultants assist clients via Matthew D’Agati.
      Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.