2
\$\begingroup\$

Problem:

Given a string aaabbcccaad print the no. of occurrence of the character in the same order in which the character occurred.

Expected output: (a, 3), (b, 2), (c, 3), (a, 2), (d, 1)

The approach:

  1. Loop through each character.
  2. When the next character is not same as the current character, record the next character and its position.
  3. count of occurence = Iterate the pos_list (position list ), take the difference
  4. Return character and its count in in the same order

Solution:

def seq_count(word):
    wlen = len(word)
    pos = 0
    pos_list=[pos]
    alph = [word[0]]
    result = []

    for i in range(wlen):
        np = i+1
        if np < wlen:
            if word[i] != word[i+1]:
                pos = i+1
                pos_list.append(pos)
                alph.append(word[i+1])
    pos_list.append(wlen)

    for i in range(len(pos_list)-1):
        result.append((alph[i], pos_list[i+1] - pos_list[i]))
    return result

print seq_count("aaabbcccaad")

Note:

I know this may not be the conventional solution, i was finding difficult to count the character and maintain its count as we iterate through the string, since I'm a beginner in python. Pls let me know how can i do it better.

\$\endgroup\$
3
\$\begingroup\$

Problems like this tend to be annoying: so close to a simple solution, except for the need to be adjusting state during the loop. In this case, itertools.groupby() offers a shortcut, because its grouping function defaults to an identity, which is exactly what you need.

from itertools import groupby

def seq_count(word):
    return [
        (char, len(tuple(g)))
        for char, g in groupby(word)
    ]

If you don't want to use another library, you can reduce the bookkeeping a bit by yielding rather than returning and by iterating directly over the characters rather than messing around with indexes. But even with such simplifications, tedious annoyances remain. Anyway, here's one way to reduce the pain a little. The small code comments are intended to draw attention to the general features of this pattern, which occurs in many types of problems.

def seq_count(word):
    if word:
        # Initialize.
        prev, n = (word[0], 0)
        # Iterate.
        for char in word:
            if char == prev:
                # Adjust state.
                n += 1
            else:
                # Yield and reset.
                yield (prev, n)
                prev, n = (char, 1)
        # Don't forget the last one.
        if n:
            yield (prev, n)

exp = [('a', 3), ('b', 2), ('c', 3), ('a', 2), ('d', 1)]
got = list(seq_count("aaabbcccaad"))
print(got == exp)    # True
\$\endgroup\$
2
  • \$\begingroup\$ Thanks! The first solution looks really good. But most of the interviewers won't accept that. Any suggestions to improve upon these kinda solution thinking? \$\endgroup\$ – dm90 May 20 at 18:30
  • 2
    \$\begingroup\$ @ManivG Find better interviewers! Mostly I'm joking, but not entirely. Don't forget that you are interviewing them too. Sensible interviewers will reward a candidate familiar with the full power of a language (eg knowing itertools), even if they also ask for a roll-your-own solution. As far as improving, I advise lots of practice trying to solve practical problems (eg on StackOverflow or here). Place less emphasis on problems requiring semi-fancy algorithms and focus heavily on bread-and-butter questions. Pay attention to how different people solve such problems and steal their ideas. \$\endgroup\$ – FMc May 20 at 18:50
1
\$\begingroup\$

For a recent version of Python (>= 3.7 I think), a dict is ordered by the insertion order of the keys. A collections.Counter() is a subclass of dict, so it is also ordered. The simplest solution is to use a Counter:

from collections import Counter

def seq_count(word):
    return list(Counter(word).items())
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.