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.
def merge_the_tools(string, k):
from collections import OrderedDict
l=[]
for i in range(0,len(string),k):
a=string[i:i+k]
l.append("".join(OrderedDict.fromkeys(a)))
for j in range(0,len(l)):
print(l[j])
My first pass used a collector list to check duplicates (and passed).
I then realised you can simply check the output for duplicates as you build it. I used string concatenation over list/ join
im afraid its not, thats not how o(n^2) works, since the first loop only iterates through every kth value in the list, so O(n/k) and the second loop
checks for k number of characters in a string so its O(k)
for each value of i a complete 'for loop' of j occurs. Like in first loop i = 0 the j will work on each value of string[0 : 0+k]. After the for loop of j finishes i will move to k as the 3rd argument in i's for loop in k which indicates the skip value and j will then loop over string[k : k+k]. This goes on till i < len(string).
for j in string[.....], j takes each value of the string in every loop and checks below conditions. If the conditions are satisfied then j will be added to a new string 's'.
thanks for the code !!!!!. bt please can u just expain the for loop .. i got bit confused in for x in xrange(0, n, k):
1 st iteration it is [0:3] 2 nd [3:6] n 3 rd [6:9] ryt ??
s[8] is not present ryt , it should give error na ?? bt it is exceuting perfectly
His code is also O(n). He has nested looping but each character is touched exactly once. The outer look is executed n/k times and the inner loop k times, so total n.
Also, in your code, the check if item not in temp would be linear on the size of temp in case of a list. The complexity of your code is O(n*k). You should use a set instead. That will reduce complexity to O(n).
I used list. But the problem is it gives unexpected order of elements. So we are not sure if output will be 'AB' or 'BA'. Also, it changes after every runtime.
You need a list as well as a set. The set for the in query, to check if we've seen this before and the list to maintain the output.
Membership query is O(n) in a list, ~O(1) in a set/dict.
The problem I am facing with this code is that, the output is not in the same order of what is expected, although repeating elements are removed.
defmerge_the_tools(string,k):#get list of indexind=[iforiinrange(0,len(string)+1,k)]#get substrings equivalent to block sizeunsetEl=([string[ind[i]:ind[i+1]]foriinrange(0,len(ind)-1)])setEl=[]#apply set funtion to each substringforiinunsetEl:setEl.append(set(i))#print dataforiinrange(len(setEl)):print(''.join(setEl[i]))
I ran some tests on this code (by @v3gA92) versus the iter example that got the most votes on here so far. This code, even though it is described as "verbose", increases performance significantly over the other. In the comparison I did, straight up loops took close to 6.something ms when I fed in a large test case and had timeit() run it 1000 times. The "iter" example using "zip" that so many people voted for reduced this down to 1.something ms for a performance boost that was six-fold. But your code example above using loops, being a little "verbose" but then deploying a list comprehension in a strategic location, boosted the original by a factor of 3 decimal places with a timeit() metric on my machine that was only 689 us (micro seconds verus milliseconds). I am learning from all of these posts so I am glad people came up with these options regardless.
if y not in uni
Even though we are checking uni time,it does not produce the complexit of O(n*k). As unique can only hold a maximum of allowed string character.
i.e if only capitals are allowed in string,then unique can have maximum of 26 length.For,for each letter of string(size(N)),search will cost maximum of 26 steps.
so total complexity will be O(N*constant value) = O(N).
The loop iterate over every character one by one, filling in the "temp" with unique characters. So if you have a string 'AADAAC' it will fill in 'A' then eventually 'D' and finally 'C'. Once length reaches limit k, the unique characters found are joined so you get 'ADC'.
Hi, I came up with this, not gonna lie, did do some google searches to get the imports. Can you comment on the time complexity as well as over all effectiveness and how I could improve it yet still maintaining readability.
importtextwrapfromcollectionsimportOrderedDictdefmerge_the_tools(string,k):list2=[]#devides string into n equal parts of size klist1=textwrap.wrap(string,k)foriinlist1:#removes duplicate characters from string and append it to list 2list2.append("".join(OrderedDict.fromkeys(i)))foriinlist2:print(i)
from collections import OrderedDict
import textwrap
def merge_the_tools(string, k):
b=textwrap.wrap(string,k)
for i in range (len(b)):
print("".join(OrderedDict.fromkeys(b[i])))
#no need to append data to list 2 it is unnecessary directly print result.
thanks for this sweet and simple solution
but why mine solution isn't working
def merge_the_tools(string, k):
length=int(len(string)//k)
l=wrap(string,length)
for i in l:
string_list=list(i)
new_list_for_new_string=[]
for c in string_list:
if c not in new_list_for_new_string:
new_list_for_new_string.append(c)
print("".join(new_list_for_new_string))
hey this is a great solution....
I adapted your code without using join() and list
def merge_the_tools(string, k):
div=len(string)//k
subword=""
l=0
for i in string:
l+=1
if i not in subword:
subword+=i
if l == k:
print(subword)
subword=""
l=0
I believe this answer would be slightly more Pythonic because it doesn't track the index manually like in the above solution.
def merge_the_tools(S, K):
temp = []
for i, letter in enumerate(S):
if letter not in temp:
temp.append(letter)
if i in range(K-1,len(S),K):
print(''.join(temp))
temp = []
Merge the Tools!
You are viewing a single comment's thread. Return to all comments →
Your code is very nice, but I think that overall complexity is quite high - O(n*n) - when compared to a simpler albeit more verbose approach:
def merge_the_tools(string, k): from collections import OrderedDict l=[] for i in range(0,len(string),k): a=string[i:i+k] l.append("".join(OrderedDict.fromkeys(a))) for j in range(0,len(l)): print(l[j])
Similar Approach .
Only Two test case passed with this approach
My first pass used a collector list to check duplicates (and passed). I then realised you can simply check the output for duplicates as you build it. I used string concatenation over list/ join
Based on other solutions you could make it even simpler
excellent
thanks very much in solving this query
excellent !! but the only drawback is time complexity
As far as I understand it's O(n). First for loop is O(n/k), second is O(k).
Yes
isnt it o(n^2) because of 1 for loop inside another
im afraid its not, thats not how o(n^2) works, since the first loop only iterates through every kth value in the list, so O(n/k) and the second loop checks for k number of characters in a string so its O(k)
O(n/k * k) = o(n)
can someone explain this nested loop??
for each value of i a complete 'for loop' of j occurs. Like in first loop i = 0 the j will work on each value of string[0 : 0+k]. After the for loop of j finishes i will move to k as the 3rd argument in i's for loop in k which indicates the skip value and j will then loop over string[k : k+k]. This goes on till i < len(string).
for j in string[.....], j takes each value of the string in every loop and checks below conditions. If the conditions are satisfied then j will be added to a new string 's'.
Here is a quick one:
for i in range(0, len(string), k): print(''.join(set(string[i:i+k])))Did this work? Because items in sets are unordered and we cannot be sure in which order they get displayed.
thanks for this simple explanation. helped me immensly.
Thanks
Most logical solution so far!
can you tell me how the line of code works for j in string[i : i + k]: because i only seen for loop with range only can anyone answer my question ?
Though it might work, it has two for loops ! which increases the complexity of the code to N power 2 times. :(
Looking for a answer where it is solved simple.
First
forloop isn/kloops then we iterate overkitems in each of then/kslices. Therefore code is O(n/k * k) = O(n)See avmohan's response below as well
**bro did the same! ** for i in range(0,len(string),k): a="".join(dict.fromkeys(string[i:i+k])) print(a)
thanks for the code !!!!!. bt please can u just expain the for loop .. i got bit confused in for x in xrange(0, n, k): 1 st iteration it is [0:3] 2 nd [3:6] n 3 rd [6:9] ryt ?? s[8] is not present ryt , it should give error na ?? bt it is exceuting perfectly
same but idk why i used this :
def merge_the_tools(string, k): ** for i in range (len(string)//k): ss=string[i*k:i*k+k]**His code is also O(n). He has nested looping but each character is touched exactly once. The outer look is executed n/k times and the inner loop k times, so total n.
Also, in your code, the check
if item not in tempwould be linear on the size of temp in case of a list. The complexity of your code is O(n*k). You should use a set instead. That will reduce complexity to O(n).I used list. But the problem is it gives unexpected order of elements. So we are not sure if output will be 'AB' or 'BA'. Also, it changes after every runtime.
You need a list as well as a set. The set for the in query, to check if we've seen this before and the list to maintain the output. Membership query is O(n) in a list, ~O(1) in a set/dict.
Below is verbose code for the same.
The problem I am facing with this code is that, the output is not in the same order of what is expected, although repeating elements are removed.
A set is an unordered collection of items, and you may get different output.
Amazing code! Simple logic
I ran some tests on this code (by @v3gA92) versus the iter example that got the most votes on here so far. This code, even though it is described as "verbose", increases performance significantly over the other. In the comparison I did, straight up loops took close to 6.something ms when I fed in a large test case and had timeit() run it 1000 times. The "iter" example using "zip" that so many people voted for reduced this down to 1.something ms for a performance boost that was six-fold. But your code example above using loops, being a little "verbose" but then deploying a list comprehension in a strategic location, boosted the original by a factor of 3 decimal places with a timeit() metric on my machine that was only 689 us (micro seconds verus milliseconds). I am learning from all of these posts so I am glad people came up with these options regardless.
logical,readable and well illustrated.
if y not in uni Even though we are checking uni time,it does not produce the complexit of O(n*k). As unique can only hold a maximum of allowed string character. i.e if only capitals are allowed in string,then unique can have maximum of 26 length.For,for each letter of string(size(N)),search will cost maximum of 26 steps. so total complexity will be O(N*constant value) = O(N).
A set is unordered. Joining the set to recreate the string would create a different order.
I believe that the set is being used to check for duplicates as
ois the output list.You are right. Figured that out after that comment. Cheers.
please explain how you break the string in pair example: "AS" "AC"
The loop iterate over every character one by one, filling in the "temp" with unique characters. So if you have a string 'AADAAC' it will fill in 'A' then eventually 'D' and finally 'C'. Once length reaches limit k, the unique characters found are joined so you get 'ADC'.
import textwrap
textwrap.wrap(string,k)
Awesome logic with simple code
Hi, I came up with this, not gonna lie, did do some google searches to get the imports. Can you comment on the time complexity as well as over all effectiveness and how I could improve it yet still maintaining readability.
Thanks in advance
can anybody explain OrderedDict.fromkeys(i) this statement?
You dont need list2 and append it. just print the output in for loop itself.
There is no need of appending it to list and having a new loop to print. Also time complexity of this solution is O(n) which is quite good!!
import textwrap from collections import OrderedDict
def merge_the_tools(string, k): source_list = textwrap.wrap(string,k) for var in source_list: print("".join(OrderedDict.fromkeys(var)))
from collections import OrderedDict import textwrap def merge_the_tools(string, k): b=textwrap.wrap(string,k) for i in range (len(b)): print("".join(OrderedDict.fromkeys(b[i])))
Thanks :)
Good approach
thanks for this sweet and simple solution but why mine solution isn't working def merge_the_tools(string, k): length=int(len(string)//k) l=wrap(string,length)
hey this is a great solution.... I adapted your code without using join() and list def merge_the_tools(string, k): div=len(string)//k subword="" l=0 for i in string: l+=1 if i not in subword: subword+=i if l == k: print(subword) subword="" l=0
cool!
print l
string_list=list(i)
thank u
This is beautiful code. Thank you.
good one
You don't need a list for it
best code the approch im looking for same idea just not clear where if and was using two loops thanks good skills
This is the best solution. Just using core python keywords with O(n) runtime
I believe this answer would be slightly more Pythonic because it doesn't track the index manually like in the above solution.
def merge_the_tools(S, K): temp = [] for i, letter in enumerate(S): if letter not in temp: temp.append(letter) if i in range(K-1,len(S),K): print(''.join(temp)) temp = []
merge_the_tools("AABCAAADA", 3)
Simple, yet affective. Congrats!
i have writen similar code but i seperated strings of length k it isO(n*n) but ur logic is super
You are using the expression
with temp defined as type list
That's not very efficient - it requires a list scan. If you use a set, it will have O(1) hash key lookup
well this one also has a high complexity coz of using that "in" keyword on a "list" use dictionary instead. :)
I really love your code
why append, just simply concat:
def merge_the_tools(string, k):
def fill(s):
You can replace temp = [] with empty string "" then use temp += in the for loop.
why these brilliant algorithms don't come to my brain -_-
I have tried exactly this and is quite simple for beginners to understand