1

Given a string, say s="##$$$#", how can I find the index where the number of "#" symbols before the index is equal to the number of "$" symbols after the index?

Example: if s="##$$$#", then the output would be 2.

Explanation: before index 2 we have 2 "#" symbols and after index 2 we have 2 "$" symbols

I tried finding the mid index first and count the symbols(# and $) on both the sides,if they are equal then print the mid index else increment the mid and proceed the same way.. But I'm not able to get the logic correctly.

miradulo
  • 28,857
  • 6
  • 80
  • 93
Rajesh s
  • 175
  • 1
  • 8

4 Answers4

0

An approach is :

At any given index 'i' ,
Count_Pound[i] = Count_Pound[i-1] + 1 if charAt(i-1) is '#' 
               = Count_Pound[i-1] if charAt(i-1) is '$'
E.g. Count_Pound[0] = 0;
     Count_Pound[1] = 0 + 1 if charAt(0) = '#'
                    = 0 if charAt(0) is '$'

Similar approach holds when you traverse in the reverse direction.

Count_Dollar[j] = Count_Dollar[j+1] + 1 if charAt(j+1) is '$'
                = Count_Dollar[j+1] if charAt(j+1) is '#'
E.g. Count_Dollar[str.length -1] = 0
     Count_Dollar[str.length - 2] = 0 + 1 if charAt(str.length-1) is '$'
                                  = 0 if charAt(str.length-1) is '#'

Once you have these two arrays after traversing forward and reverse ways - BTW you could have these two arrays built in just one loop, have two indices one incrementing and one decrementing. Then go through these arrays and get the largest ( I am assuming you want the largest ).

for i : 0 to str.length-1:
    if Count_Pound[i] == Count_Dollar[i] && max_value < Count_Pound[i]
          max_value = Count_Pound[i]
          ans = i

return ans

Space complexity is not bad : O(n), time complexity is good : O(n)

SomeDude
  • 13,876
  • 5
  • 21
  • 44
0

Could you try using a for loop to test each place in the string? From what I can gather, it seems when you said index 2 is the answer, the index itself is excluded so you get str[:index] to str[index+1:]

So you'd get something like this:

def half(str, first_half, second_half):
    for i in range(len(str)):
        if str[:i].count(first_half) == str[i+1:].count(second_half):
            return i
    return None
N Chauhan
  • 3,407
  • 2
  • 7
  • 21
0

This one should scale as O(N):

def same_count(s):
    c1 = 0
    c2 = 0
    l1 = list()
    l2 = list()
    n = len(s)
    for i in range(n):
        # count forward from start
        if s[i] == '#':
            c1 += 1
        # count backward from end
        if s[n - i - 1] == '$':
            c2 += 1
        l1.append(c1)
        l2.append(c2)
    # reverse second list
    l2 = list(reversed(l2))
    # find index where counts are the same
    match = [i for i in range(1,n-1) if 
         l1[i-1] == l2[i+1]]
    if match:
        return match[0]
    else:
        return None


print(same_count('##$$$#'))
print(same_count('###$$$##'))
print(same_count('#$$'))

#output:
#2
#None
#1
Yosi Hammer
  • 588
  • 2
  • 8
0
string = '##$$$#'
foundHash = False
foundDollar = False
dollarIndex = -1
hashCount = 0
dollarCount = 0

for i,c in enumerate(string):
    if c == '#' and not foundHash:
        hashCount = hashCount + 1
        foundHash = True
    elif c == '#' and foundHash and not foundDollar:
        hashCount = hashCount + 1
    elif c == '$' and foundHash and not foundDollar:
        dollarIndex =  i
        foundDollar = True
    elif c == '$' and foundHash  and foundDollar:
        dollarCount =  dollarCount + 1
    else:
        if hashCount == dollarCount:
            break
        else:
            foundHash = False
            foundDollar = False
            dollarIndex = -1
            hashCount = 0 
            dollarCount = 0
            if c == '#' and not foundHash:
                hashCount = hashCount + 1
                foundHash = True

if dollarIndex > 0 and hashCount == dollarCount:
    print("index = %d" %(dollarIndex))
else:
    print("index not found")
Ramanathan Ganesan
  • 560
  • 2
  • 10