Maximum length of the substring | Sololearn: Learn to code for FREE!

+1

Maximum length of the substring

Find the length of the substring which has no repeated characters present in the string.. Like If a="bbb" Then answer should be "b" And length should be 1. All the characters in the string are connected! I want answer in O(n) but got a complexity of O(n^2)

4/4/2018 6:17:36 PM

Trivedi Rutansh

12 Answers

New Answer

+1

a = "BartoszBar" result = "" j = 0 s = [] for i in range(0, len(a) - 1): while (j < i and a[i] in s): s.remove(a[j]) j = j + 1 s.insert(a[i]) if (i - j + 1 > len(result)): result = a[j:i+1] print result Now it is linear.

+1

Nah, it is O(nlogn). It is not much slower than O(n)

+1

Now it is linear. Used list instead of set

0

Are in substring all letters connected or not necessary?

0

Yes all the letters are connected

0

You can bruteforce it. Longest answer is 26(alphabet size). Then start in any position and go on 26 letters ahead. O(26*N)=O(N)

0

Brother can you please simplify your answer? If user enters string value = "BartoszBar" Then our method should return "Bartosz" and length of 7 with O(n) Complexity

0

Wait, I will write code.

0

Okay thanks 😅

0

Bro complexity is O(n^2)

0

I want O(n) and it is feasible..😬

0

Got it..Thanks ✌🏻😬