3
\$\begingroup\$

Ok, now for some time I've been trying to conquer this challenge without success performance wise. And I'd like some hints about approaching this problem, or the general algorithms I should learn before tackling something like this.

Task description :

A string is balanced if it consists of exactly two different characters and both of those characters appear exactly the same number of times. For example: "aabbab" is balanced (both 'a' and 'b' occur three times) but "aabba" is not balanced ('a' occurs three times, 'b' occurs two times). String "aabbcc" is also not balanced (it contains three different letters). A substring of string S is a string that consists of consecutive letters in S. For example: "ompu" is a substring of "computer" but "cmptr" is not. Write a function solution that, given a string S, returns the length of the longest balanced substring of S.

Examples (input -> output) :

'cabbacc' -> 4 ( 'abba')

'ab' -> 2 ('ab')

'abababa' -> 6 ('ababab' / 'bababa')

'abc' -> 2 ('ab'/'bc')

'bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbaabbabbbbbbbbbbbbb' -> 6 ('baabba')

etc.

I have tried solving it in number of different ways , but here is the last one that gave me 100% on correctnes :

def solution(s):
    c = {}
    linker = {}
    for i in range(len(s) - 1, -1, -1):
        c[s[i]] = c.get(s[i],0) + 1
        linker['%s%s'%(len(s)-1,i)] = c.copy()

    c = {}
    for i in range(0, len(s)):
        c[s[i]] = c.get(s[i],0) + 1
        linker['%s%s'%(0,i)] = c.copy()


    window_size = len(s) if len(s) % 2 == 0 else len(s) - 1
    if len(s) % 2 == 0:
        check = linker['%s%s'%(len(s)-1,0)]
        if(len(check) == 2):
            if list(check.values())[0] == list(check.values())[1]:
                return window_size

    everything = linker["%s%s"%(len(s)-1,0)]
    #print("WIdnow size : " ,window_size )
    for ws in range(window_size, 0, -2):
        for i in range(0,len(s)-ws+1):
            sp_inc = i
            ep_inc = i+ws
            #print(sp_inc,ep_inc )


            d1 = dict()
            d2 = dict()
            if sp_inc-1 >= 0:
                d1 = linker["%s%s"%(0,sp_inc-1)]
            if ep_inc <= len(s)-1:
                d2 = linker["%s%s"%(len(s)-1, ep_inc)]
            #print(d1,d2,everything)
            result = dict()
            for k,v in everything.items():
                result[k] = v - d1.get(k,0) - d2.get(k,0)
                if(result[k] == 0):
                    del result[k]
            if len(result) == 2:
                if list(result.values())[0] == list(result.values())[1]:
                    #print(result)
                    return ws





    return 0


tests = [
    ["cabbacc", 4],
    ["ab", 2],
    ["abababa", 6],
    ["abc", 2],
    ["ababbbaa", 8],
    ['bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbaabbabbbbbbbbbbbbb',6],
    ['aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaa',70]


]


for i in tests:
    print(i[0])
    #assert solution(i[0]) == i[1]
    assert solution(i[0]) == i[1]
   # break
print("everything ok")

Here is another approach I tried, but it wasn't totally correct ( for some test cases it gave me result that was equal to correct_result + 2 ), but for all test cases in tests array it gave me correct result.

from collections import deque


def solution(s):
    #print(s)
    window_size = len(s)
    chars = {}
    old_window = deque()    
    for d in s:
        chars[d] = chars.get(d,0) + 1
        old_window.append(d)


    #print(chars)
    if len(chars) == 2 and window_size % 2 == 0:
        if chars[list(chars.keys())[0]] == chars[list(chars.keys())[1]]:
            return window_size

    if(window_size % 2 == 0):
        window_size-= 2
        c = old_window.pop()
        chars[c]-=1
        if chars[c] == 0:
            del chars[c]
        c = old_window.pop()
        chars[c]-=1
        if chars[c] == 0:
            del chars[c]
    else:
        window_size-= 1
        c = old_window.pop()
        chars[c]-=1
        if chars[c] == 0:
            del chars[c]


    if len(chars) == 2 and window_size % 2 == 0:
        if chars[list(chars.keys())[0]] == chars[list(chars.keys())[1]]:
            return window_size
    #return None

    #print(s[len(old_window)]);
    #return None
    flow = 1

    while(window_size > 0):
       # print("Hello")
        if flow == 1:
           # print("Here", len(old_window)+1,len(s))
            for i in range(window_size,len(s)):
                c = old_window.popleft()
                #print("char poped %s"% c)
                chars[c]-=1
                if chars[c] == 0:
                    del chars[c]
                old_window.append(s[i])
                #print("Hello " , old_window)
                chars[s[i]] = chars.get(s[i],0) + 1
                if len(chars) == 2:
                    if chars[list(chars.keys())[0]] == chars[list(chars.keys())[1]]:
                        #print("".join(old_window))
                        return window_size
                #print(":" , "".join(old_window))
            flow = 0
        else:
            for i in range(len(s)-window_size-1,-1,-1):
                c = old_window.pop()
                chars[c]-=1
                if chars[c] == 0:
                    del chars[c]
                old_window.appendleft(s[i])
                #print(old_window)
                chars[s[i]] = chars.get(s[i],0) + 1
                if len(chars) == 2:
                    if chars[list(chars.keys())[0]] == chars[list(chars.keys())[1]]:
                        #print("".join(old_window))
                        return window_size
                #print(":" , "".join(old_window))
            flow = 1

        for i in range(2):
            if flow == 1:
                c = old_window.pop()
                chars[c]-=1
                if chars[c] == 0:
                    del chars[c]
            else:
                c = old_window.popleft()
                chars[c]-=1
                if chars[c] == 0:
                    del chars[c]
        window_size-=2    

    return 0


tests = [
    ["cabbacc", 4],
    ["ab", 2],
    ["abababa", 6],
    ["abc", 2],
    ["ababbbaa", 8],
    ['bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbaabbabbbbbbbbbbbbb',6],
    ['aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaa',70]


]


for i in tests:
    print(i)
    #assert solution(i[0]) == i[1]
    print(solution(i[0]))
\$\endgroup\$
  • \$\begingroup\$ Why cabbac is not a solution in the first example? \$\endgroup\$ – vnp Oct 2 '18 at 0:06
  • \$\begingroup\$ there must be only two different letters in substring :) \$\endgroup\$ – Marko Mackic Oct 2 '18 at 0:07
  • \$\begingroup\$ Oh. Missed that. \$\endgroup\$ – vnp Oct 2 '18 at 0:08
  • \$\begingroup\$ What do you mean by “without success performance wise”. You have 100% success. Is this a timed challenge and you’re getting a time-limit-exceeded? \$\endgroup\$ – AJNeufeld Oct 2 '18 at 4:09
  • \$\begingroup\$ I'm getting timeout error for performance check test cases :) \$\endgroup\$ – Marko Mackic Oct 2 '18 at 6:14
5
+50
\$\begingroup\$

1. Review

Just reviewing the first (working) version of the code. Some of the points here were also made in AJNeufeld's answer.

  1. I found the code a bit hard to read. For example, what does this code do?

    linker = {}
    c = {}
    for i in range(0, len(s)):
        c[s[i]] = c.get(s[i],0) + 1
        linker['%s%s'%(0,i)] = c.copy()
    

    It takes some effort to figure out that this builds a mapping from i to a dictionary of counts of characters in the substring s[:i+1]. So this could be clarified by renaming some of the variables and adding a comment:

    # Mapping from i to counts of characters in s[:i+1].
    prefix_counts = {}
    counts = {}
    for i in range(0, len(s)):
        counts[s[i]] = counts.get(s[i],0) + 1
        prefix_counts[i] = counts.copy()
    
  2. Python provides the data structure collections.Counter, for counting things:

    # Mapping from i to counts of characters in s[:i+1].
    prefix_counts = {}
    counts = Counter()
    for i in range(0, len(s)):
        counts[s[i]] += 1
        prefix_counts[i] = counts.copy()
    
  3. When iterating simultaneously over the indexes i and elements s[i] of a sequence s, it's convenient to use the built-in function enumerate:

    # Mapping from i to counts of characters in s[:i+1].
    prefix_counts = {}
    counts = Counter()
    for i, c in enumerate(s):
        counts[c] += 1
        prefix_counts[i] = counts.copy()
    
  4. The prefix_counts data structure would be easier to understand if it were a mapping from i to counts of characters in s[:i] (not s[:i+1]. This would avoid the need to subtract one later on.

  5. The counts of characters in s[i:] should go in a different mapping, for example suffix_counts, instead of trying to pack them into the same mapping as the prefix counts.

  6. The computation of the maximum window size:

    window_size = len(s) if len(s) % 2 == 0 else len(s) - 1
    

    could be simplified to:

    window_size = len(s) // 2 * 2
    
  7. But in fact we don't need to compute it at all, because we can use reversed:

    for ws in reversed(range(2, len(s) + 1, 2)):
    
  8. There's a special case for checking if the whole string is balanced. But this special case is unnecessary as the main loop will also check this case.

  9. The condition if sp_inc-1 >= 0: could be avoided by adding an entry for -1 to the prefix_counts mapping.

  10. Instead of computing everything minus suffix_counts[i + ws] minus prefix_counts[i], compute prefix_counts[i + ws] minus prefix_counts[i]. This avoids the need for everything and suffix_counts.

  11. Since we are using collections.Counter, we can just subtract the counter objects without the need to loop over the items:

    window_counts = prefix_counts[i + ws] - prefix_counts[i]
    
  12. Instead of calling result.values() twice:

    if list(result.values())[0] == list(result.values())[1]:
    

    Call it once and use tuple unpacking to assign names to its two elements:

    v, w = window_counts.values()
    if v == w:
    

2. Revised code

from collections import Counter

def solution(s):
    """Return the length of the longest balanced substring of s."""
    counts = Counter()
    prefix_counts = {} # Mapping from i to counts of characters in s[:i].
    for i, c in enumerate(s):
        prefix_counts[i] = counts.copy()
        counts[c] += 1
    prefix_counts[len(s)] = counts
    for window in reversed(range(2, len(s) + 1, 2)):
        for i in range(len(s) - window + 1):
            window_counts = prefix_counts[i + window] - prefix_counts[i]
            if len(window_counts) == 2:
                v, w = window_counts.values()
                if w == v:
                    return window
    return 0

3. Complexity

If the string has length \$n\$ and there are \$k\$ distinct characters, then there are \$O(n)\$ lengths for the window, \$O(n)\$ positions for the start of the window, and it takes \$O(k)\$ to do the subtraction of the prefix counts, so the overall runtime is \$O(kn^2)\$.

In order to pass the time limit, you need to find a better algorithm, ideally one that runs in \$O(n)\$. I don't want to spoil the challenge for you, so I'll give you some hints.

Hint 1

Consider an easier problem first. What if you knew in advance that there were only two distinct characters in the string, for example, it only consists of a and b?

Hint 2

Instead of keeping separate counts of a and b, what if you kept a running difference between the number of a and the number of b?

Hint 3

If the string is abbbaaaaabbaa then the running differences are \$0, 1, 0, -1, -2, -1, 0, 1, 2, 3, 2, 1, 2, 3\$. How do these differences relate to the longest balanced substring?

Hint 4

What if you kept, for each value in the running differences, the minimum and maximum indexes at which the value occurred?

\$\endgroup\$
  • \$\begingroup\$ Thanks for such detailed review and helpful hints. I'll mark this answer as accepted, and award you with bounty :) \$\endgroup\$ – Marko Mackic Oct 4 '18 at 12:21
  • \$\begingroup\$ One question, you gave example where balanced substring is at the beginning. What if it's inside, let's say aaaaaaabbbaaabbb, so running differences are 0, 1,2,3,4,5,6,7,6,5,4,5,6,7,6,5,4 and the longes balanced substring is aaabbbaaabbb . I see the declining and rising pattern in differences but i don't know how I can conclude it's balanced. In first example it was 0 because it was beginning. \$\endgroup\$ – Marko Mackic Oct 4 '18 at 14:30
  • \$\begingroup\$ What are the values for the running difference at the start and end of the balanced substring? \$\endgroup\$ – Gareth Rees Oct 4 '18 at 14:33
2
\$\begingroup\$

It has taken me a while, but I think I understand what you are doing now. And I’ve got some improvements. I’m only going to consider your code that passes 100%. (Your code that doesn’t work properly in all cases is not appropriate for review on Code Review.)


First, you compute len(s)-1 in many places. You should compute it once and store it in a local variable.


You compute the letter counts and store it in:

  • linker["%s%s" % (len(s)-1, i)] and
  • linker["%s%s" % (0, i)]

These are really 2 separate dictionaries, both counting characters from each end of the string. It takes time to create the tuple, format it into the string, and then use that string as the dictionary key.

Why not simply use two dictionaries? Say forward[i] and backward[i]?


d1 = dict()
d2 = dict()

You unconditionally create these dictionaries, and then throw them away in most cases. Creating dictionaries takes time. Use an else: clause and only create them when needed.


result[k] = ...
if result[k] == 0:
    del result[k]

You do a calculation, create a dictionary entry, look up the dictionary entry, test it for zero, and delete the entry if it was. Seems like we can make some large gains here.

temp = ...
if temp != 0:
    result[k] = temp

if list(result.values())[0] == list(result.values())[1]:

Take a dictionary, create a view of values only, convert it to a list, take only the first element from the list, and then... Take the same list, create another view of values, convert it into another (identical) list, and take the second value from the list. Finally, compare the two values.

Very inefficient!

How about:

x, y = result.values()
if x == y:

To count the middle elements between i & j only, you do evaluate everything - forward[i] - backward[j].

I don’t think you need everything or backward[ ] at all. You could just use forward[j] - forward[i].

\$\endgroup\$
  • \$\begingroup\$ All of these are valid improvements, I'll apply them, and if they pass, I'll mark your answer as accepted. Thanks :) \$\endgroup\$ – Marko Mackic Oct 3 '18 at 10:57
  • \$\begingroup\$ Refactored and still times out, there must be different approach to this problem, that's what I'm seeking for. Here is refactored code in pastebin (pastebin.com/P5xPFrZj ) , so you know I've tried it. It seems it detects complexity of O(n^2) and that's not satisfying. \$\endgroup\$ – Marko Mackic Oct 3 '18 at 12:58
  • \$\begingroup\$ You haven’t made the del result[k] change, and you still have both forward and backward dictionaries, so you haven’t made all the improvements. Still, with for ws ... for i ... for k,v ..., I wouldn’t be surprised to see a report of \$O(n^3)\$. My suggestions were to improve your existing code. I’ll have to think on improving your algorithm. \$\endgroup\$ – AJNeufeld Oct 3 '18 at 22:39

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.