Strings

Question 1

Longest Common Prefix

Answer 1

easy method is to use associative property and calculate common prefix one by one for each common string. O(mn)

find the string with least length
check for each character it is present in each string and append return the result when mistmatched o (MN)

Question 2

Implement strtsrt

Answer 2

Standard O(mn) solution where we check the inner string in from all points when return i using j as moving pointer.

Question 3

Implement atoi (string to int) “123” to 123

Answer 3

1. remove first whitespaces
2. check for the sign
3. add the number = number * 10 + (int)string[i] ;

Question 4

Longest Distinct Characters in the string

Answer 4

We go from left to right maintaining max_len.

foreach char we check if it was found previously.
if not found we maintain the index of this char in an array or map and increase cur_len
else
we calculate the leng with i - prev_index
and update if greater than max_len

lastly we check again if the cur_len is greater thjan max_len

Question 5

two strings are anagrams of each other or not

Answer 5

1. use sorting and check if each character is same or not
2. Count the characters using char arrays
3. Use xoring

Question 6

Form a palindrome

Answer 6

we use dp here to because the recursive method has overlapping subprblems,

we fill the table in a gap structure
this is the dp condtion
for(gap = 1; gap < n; gap++){
for(l - 0; h = gap; h < n; h++){
table[l,h] = str[l] == str[h]? table[l + 1, h -1] : Math.Min(table[l, h-1],table[l +1,h]) + 1;
}
}

check once after filling table

Question 7

Remove Duplicates

Answer 7

use hash set and convert it into a strnig. o(N)