Closed sebastien988 closed 3 years ago
hey, may I help?
Hi There I was learning some Program on Python there I worked on example program which will return me a distinct element substring from a given string. Ex
res = '' for i in str1: if i not in res: res = res+i else: l_res = res res = i
if len(l_res) > len(res): res = l_res
print(res)
In this example I have used the not in Python Built in method, So here I wanted to know am I increasing any time complexity on the program
Pretty sure you can make this shorter @KlassiC-man can you help out here?
I am not exactly getting what you want to do here @vdubbaka727 Could you explain it more clearly please in simpler words because I am not getting what exactly you want...
If you want to concatenate strings unless they are of same length then you must use a while loop instead of a for loop
Like:
while len(str1) < len(str2):
str1 + whatever you want to add
The distinct element sub sting Is a string where the string will have all the district alphabets with maximum length
In this example for every iteration I am checking for new alphabet weather it is existing in the result or not by using is in inbuy method. Will it going to cost me any time complexity , please suggest
It might slow down your code for some 2 to 3 seconds or maybe even less because you are trying to go through all the districts right... and its not something you need to worry about that much so this method should also work out for ya 😄!
Well, your code is longer, hence it will definitely cost you some time, but it shouldn't make much of a difference as it will hardly be a 5 milli second gap, however if this does bother you, try making your code shorter, I think @KlassiC-Man can handle this, byee!
As mentioned above, this method will not be a problem since the code is short. It took 102 µs when I ran your code. If I understood your problem correctly, this piece of code took 55 µs time.
print("".join(set(str1)))
We can't interpret it literally by looking at µs , but with longer strings this difference will be even greater. I'm sure someone else will come up with a better solution. ;)
@ozgurdogan646 Your solution might not work if we're given with the constraint of not changing the order of characters in the string. As set()
might change the order of characters.
What I think is like, now it's giving the time complexity of O(n)...But if we traverse through the string from both start and end, and simultaneously, check the occurrence of both characters in res
, It will take O(n/2) time complexity.
And I think It will be best solution, if we will not use any in-built method.
Solution Github copilot came up with
def largest_substring_consisting_of_unique_elements(s: str) -> str:
"""
this function returns the largest substring with all unique elements
"""
if not s:
return ""
if len(s) == 1:
return s
max_len = 0
max_substring = ""
for i in range(len(s)):
for j in range(i, len(s)):
if len(set(s[i : j + 1])) == j - i + 1:
if j - i + 1 > max_len:
max_len = j - i + 1
max_substring = s[i : j + 1]
return max_substring
def main():
print(largest_substring_consisting_of_unique_elements("abcabcbb"))
print(largest_substring_consisting_of_unique_elements("bbbbb"))
print(largest_substring_consisting_of_unique_elements("pwwkew"))
print(largest_substring_consisting_of_unique_elements("a"))
print(largest_substring_consisting_of_unique_elements("abcdab"))
main()
output:
abc b wke a abcd
Hey @cclauss, should we close this issue?
hello