We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. How Many Substrings?
  5. Discussions

How Many Substrings?

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 64 Discussions, By:

votes

Please Login in order to post a comment

  • yiqunwang_lisa
    5 years ago+ 1 comment

    Can't pass test case#4 and onwards... Any help optimizing the following python 3?

    newS=s[left:right+1]

    sub=[newS[i:i+j] for j in range(1,len(newS)+1) for i in range(len(newS)-j+1)]

    print(len(set(sub)))

    9|
    Permalink
  • kuanwu01
    3 years ago+ 1 comment

    Since this is a discussion, I will just put here: The main problem is counting unique substrings. This is not done by simple combinatorics (I know the formulas and it doesn't work here). It is also not done by double for-loops to add all possible strings to a set/list (less repeated ones), as that has to be done in O(n^2).

    This problem has to be done in O(n). I don't have the exact solution, but I'm guessing it is probably done by a suffix tree. And one of the only ways to build a suffix tree in O(n) time complexity is using Ukkonen's algorithm. It's not as simple as you think. Google it and find out. Most of the codes posted here (as are those i'm able to come up with) have too high a time complexity to past the latter cases. The algorithm is named for a reason. And this is expert for a reason.

    5|
    Permalink
  • wryan42675
    4 years ago+ 0 comments

    I have yet to start writing code on this, but I'm thinking that it might be good to build a suffix array augmented with LCP array. I know that they can be used to quickly count the number of distinct substrings of a given string. But I'm still strugling to figure out how to deal with multiple queries, quickly counting substrings of a substring?

    2|
    Permalink
  • raihanjashil
    7 months ago+ 1 comment

    New to python here thats why the lengthy code:

    def countSubstrings(s, queries):
        endresult = []
        for i in range(len(queries)):
            
            left = queries[i][0]
            right = queries[i][1]+1
            sub = s[left:right]
            a,r,k = '',[],[]
            if len(sub) == 1 or len(sub) == 0:
                endresult += [len(sub)]
                continue
            
            else:
                for i in sub:
                    if i not in r:
                        r += [i] #all unique letters added to list
                for i in range(len(sub)):
                    for j in range(i,len(sub)):
                        a += sub[j]
                        r += [a]
                    a = ''
                for i in range(len(sub)):
                    for j in range(len(sub)-1,i+1,-1):
                        a = sub[j]
                        r += [a]
                    a = ''
            
            for i in r:
                if i not in k:
                    k += [i]
            endresult += [len(k)]
        return endresult
            
    
    0|
    Permalink
  • kevinoberoy98
    10 months ago+ 0 comments

    Python 3 runtime error

    def countSubstrings(s, queries):
        # Write your code here
        arr = []
        st = ""
        for i in queries:
            st = s[i[0] : i[1] + 1]
            result = set()
        
            for i in range(len(st) + 1):
                for j in range(i + 1 , len(st) + 1):
                    result.add(st[i : j])
            
            arr.append(len(result))
        
        return arr
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature