Given a string s, find the length of the longest substring with all distinct characters.
Input: s = "geeksforgeeks"
Output: 7
Explanation: "eksforg" is the longest substring with all distinct characters.
Input: s = "abcdefabcbb"
Output: 6
Explanation: The longest substring with all distinct characters is "abcdef", which has a length of 6.
My Approach – Sliding Window
class Solution:
def longestUniqueSubstr(self, s):
# code here
char_index = {}
max_length = 0
start = 0
for i, char in enumerate(s):
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1 #crux
char_index[char] = i
max_length = max(max_length, i - start + 1)
return max_length
Given an integer array arr[]. Find the number of triangles that can be formed with three different array elements as lengths of three sides of the triangle. A triangle with three given sides is only possible if sum of any two sides is always greater than the third side.
Input: arr[] = [4, 6, 3, 7]
Output: 3
Explanation: There are three triangles possible [3, 4, 6], [4, 6, 7] and [3, 6, 7]. Note that [3, 4, 7] is not a possible triangle.
Input: arr[] = [10, 21, 22, 100, 101, 200, 300]
Output: 6
Explanation: There can be 6 possible triangles: [10, 21, 22], [21, 100, 101], [22, 100, 101], [10, 100, 101], [100, 101, 200] and [101, 200, 300]
My Approach
class Solution:
#Function to count the number of possible triangles.
def countTriangles(self, arr):
# code here
arr.sort()
n = len(arr)
cnt = 0
for itr in range(2, n):
left = 0
right = itr - 1
while left < right:
if arr[left] + arr[right] > arr[itr]:
cnt += right - left
right -= 1
else:
left += 1
return cnt
Given an array arr[] and an integer target. You have to find the number of pairs in the array whose sum is strictly less than the target.
Input: arr[] = [7, 2, 5, 3], target = 8
Output: 2
Explanation: There are 2 pairs with sum less than 8: (2, 5) and (2, 3).
Input: arr[] = [5, 2, 3, 2, 4, 1], target = 5
Output: 4
Explanation: There are 4 pairs whose sum is less than 5: (2, 2), (2, 1), (3, 1) and (2, 1).
My Approach
Sorted the array and used two pointer approach to find the possible pairs.
class Solution:
#Complete the below function
def countPairs(self, arr, target):
#Your code here
arr.sort()
n = len(arr)
cnt = 0
left = 0
right = n - 1
while right > left:
if arr[right] + arr[left] < target:
cnt += right - left
left += 1
elif arr[right] + arr[left] >= target:
right -= 1
return cnt
Given a sorted array arr[] and a target value, the task is to count triplets (i, j, k) of valid indices, such that arr[i] + arr[j] + arr[k] = target and i < j < k.
Input: arr[] = [-2, 0, 1, 1, 5], target = 1
Output: 0
Explanation: There is no triplet whose sum is equal to 1.
My Approach:
Initially i tried to approach the problem, similar to this. All testcases but 1 passed. Initial time complexity is O(n3). Failed 6 times.
class Solution:
def countTriplets(self, arr, target):
hash_set = {}
total = len(arr)
cnt = 0
# Build the hash_set with indices for each value in arr
for i in range(total):
if arr[i] not in hash_set:
hash_set[arr[i]] = []
hash_set[arr[i]].append(i)
# Iterate through all pairs (itr, jtr)
for itr in range(total):
for jtr in range(itr + 1, total):
rem = target - arr[itr] - arr[jtr]
# Check for remaining value in hash_set
if rem in hash_set:
# Use binary search to count indices greater than jtr
indices = hash_set[rem]
low, high = 0, len(indices)
while low < high:
mid = (low + high) // 2
if indices[mid] > jtr:
high = mid
else:
low = mid + 1
cnt += len(indices) - low
return cnt
Then after reading blogs, switched to Two Pointer method
class Solution:
def countTriplets(self, arr, target):
n = len(arr)
res = 0
for i in range(n - 2):
left = i + 1
right = n - 1
while left < right:
sum = arr[i] + arr[left] + arr[right]
if sum < target:
left += 1
elif sum > target:
right -= 1
else:
ele1 = arr[left]
ele2 = arr[right]
cnt1 = 0
cnt2 = 0
while left <= right and arr[left] == ele1:
left += 1
cnt1 += 1
while left <= right and arr[right] == ele2:
right -= 1
cnt2 += 1
if ele1 == ele2:
res += (cnt1 * (cnt1 - 1)) // 2
else:
res += (cnt1 * cnt2)
return res
Given an array arr[] of non-negative integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.
Input: arr[] = [2, 6, 1, 9, 4, 5, 3]
Output: 6
Explanation: The consecutive numbers here are 1, 2, 3, 4, 5, 6. These 6 numbers form the longest consecutive subsquence.
Today’s problem is similar to Two Sum problem, but with a counter.
class Solution:
#Complete the below function
def countPairs(self,arr, target):
#Your code here
hash_count = {}
total_count = 0
for num in arr:
rem = target - num
if hash_count.get(rem):
total_count += hash_count.get(rem)
hash_count[num] = hash_count.get(num, 0) + 1
return total_count
Login
