- Prepare
- Algorithms
- Strings
- How Many Substrings?
- Discussions
How Many Substrings?
How Many Substrings?
+ 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)))
+ 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.
+ 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?
+ 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 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
Sort 64 Discussions, By:
Please Login in order to post a comment