Strings Flashcards
Palindrome string
Considering only alpha numeric char and ignoring cases
Firstly convert the string to lower case
Create another string which stores only alpha numeric char present in the given string
Numbers 48-57 a-z 65-90
Then simply check if the new string is palindrome or not
Vowels and consonants
Given a string containing lower case characters, find the no. of substrings which start with vowels and end with consonants.
First count the number of vowels and consonants present. Now traverse the string. If the current char is a vowel Count+=cons as with this vowel as the start point and with the number of consonants left we can make those many substrings Vowels-- Else Count+= vowels Cons--
Return count! Simple!
Remove consecutive char
Given a string a and an integer b, remove all consecutive char that have length exactly b
Use a stack
Push the current element into the stack.
If the current element is equal to its previous then increase the count
Once the count reaches b, pop b elements from the stack and make count to 0
Now after traversing the whole array,
The stack will contain our and . So pop and add to res and finally reverse.
Longest common prefix
Given an array of strings A, find the longest string s which is the prefix of all the strings in the array.
Firstly find the smallest string in the given array because any common prefix cannot be more than this.
Then put it at index 0 of the array
Exchange it with the one at index 0
Now simply iterate through every index of the smallest string and check if the char matches with those of all other strings in the array and find the index of first mismatch
The smallest string upto that index will be the answer
Count and say
1 11 21 1211 111221….
If n=1 return 1
If n=2 return 11
We have previous string. From the previous string we should generate the current string
So the idea is to traverse through the previous string and the count the occurrence of each char. Whenever the next char doesn’t match, we make count back to 0. To the new string we keep adding ‘count’+’element’.
Length of last word
Given a string s of upper / lower case char and empty spaces, return the length of the last word in the string
Firstly deal with leading zeros and find the index at which the string actually begins.
Similarly deal with trailing zeros and find the index at which the string actually ends.
Now starting from that end index find the first empty space and maintain a count
If count==j+1
Return j+1-r ( no space a single word?)
Return j-idx
Reverse the string
Return the string after reversing it word by word
Reversed string should not contain leading or trailing spaces.
If there are multiple spaces reduce them to a single space in the reversed string.
Maintain currstr
Starting from the right end of the string,
If char== space and currstr length=0
Then simply continue as that will be a trailing space
Else if curstr is not of zero length and we have found a space, that means we have found a word. So reverse the word.
Now we have to add this word to ans .
If ans is not empty add space and then add this current word. Else directly. After adding it to the answer, make curstr empty again and go in search for the next word.
Once we finish traversing the whole string,
The last word might be left off to as i might become less than 0. And without getting space
So ensure to add it to the answer as well after reversing the word.
Finally return answer.
Amazing subarrays
Find the number of amazing substrings, those which strat with a vowel
Just at each occurance of a vowel starting from the end, count the number of subarrays from there. That would be the length from end.
Keep adding them.
But this considers duplicates as well! How then?
Integer to roman
Maintain a map for the mapping from decimal to roman numbers for 1-10. greater than Thousand is rep as M 900 as CM 500 as D 400 as CD 100 as XC 50 L 40 XL 10 X While the number is greater than 100 0 Ans+=M subtract 1000 Similarly for the rest. Then finally ans+=m[A] for single digit
Roman to integer
Starting from right, last is value of a(i) and second last is a(i-1)
If second last is less than last the Sol = sol-last
i–
Second last=0
Last=0
See the video and understand again
Power of 2
Find if a given number is a power of 2 or not
N& N-1 is 0 iff N is a power of 2
Multiply strings
Given two numbers represented as strings, return multiplication of the numbers as a string. The numbers can be arbitrarily large and are non negative. Your answer should not have leading zeros.
The maximum size of the resulting number cannot be more than num1.size + num2.size.
For i starting from the right end of num1 and j from the right end of num2, the resulting index will be at i+j+1
Num(i+j+1) += (num1(i)-‘0’)*(num2(j)-‘0’)
Num(i+j) += num(i+j+1)/10
Num(i+j+1)%=10
Then after finding the product, there might be leading zeros cause we might not used the entire length.
Starting from left, find the index where the product actually begins.
From there add the char to res
res.push_back(num[i++]+’0’)
Minimum characters required to make a string palindrome.
Can insert charector only at the beginning of the string.
Let the given string be A.
Reverse the string and concatenate it with the original string
string concat= A+’$’+rev
Compute LPs arrayof the resulting string
Char matched= LPs(LPs.size-1)
So what need to added are n- char matched
