Beginner
1. Timing Format2. Date Format3. Palindrome 4. Anagrams5. Balanced Parenthesis6. Equal Strings7. Smallest Window8. Reverse of String9. Distinct Palindromes10. Remove adjacent duplicates11. Run length encoding12. Non repeating Character13. Array of strings14. Find Excel Column15. Transform one string to another16. Move Robot in circular17. Zig Zag concatenation. 18. Min No of elements19. Combination of strings used to dial a number20. Ancient StringDistinct Palindromes
LEVEL:Beginner
Description
Given a string K. You have to find the reverse of given string.
Input Format
First line contains the string K.
Output Format
Print the number of distinct palindromes can form.
aaa
6
abaaa
5
abcd
4
Login to see Discussion
Approach
Approach 1: Using Brute Force (Note this approach gives all possible palindromes
considering the repeated ones too)
step-i) initialize count variable to 0
step-ii) initialize i to 1
step-iii) initialize j = 0
step-iv) initialize k to j+i-1 and create a new string builder
step-v) initialize l to j
step-vi) append character at index l to the string builder and increment l
step-vii) repeat step vi till l is less than or equal to k
step-viii)check if string builder and it's reverse are same or not
step-ix) if same increment the count
step-x) increment j
step-xi) repeat steps iv to x till j is less than or equal to length of string
step-xii) increment i
step-xiii) repeat steps iii to xii till i is less than or equal to lenght of string
step-xiv) return count
Time Complexity: O(n^2)
Space Complexity: O(n)
Approach 2: Using HashMap (Note : as this approach uses hashing it only gives us the count of
unique palindromes that are present in the given string)
step-i) create a 2D array dp of size n*n where n is the size of the string
step-ii)create a hash map with string as keys and boolean as values
step-iii) initialize i to 0
step-iv)assign value 1 to dp[i][i]
step-v)insert substring from i to i+2 as key and true as value in hashmap
step-vi)increment i
step-vii)repeat steps iv, v and vi till i is string length - 1
step-viii) check if character at i and i+1 are same or not
step-ix) if they are same assign 1 to dp[i][i+1]
step-x)insert substring from i to i+2 of given string as key and true as value
step-xi)else assign 0 to dp[i][i+1]
step-xii) repeat steps ix to xii till i is less than length of string -1
step-xiii) initialize len to 3
step-xiv) initialize start to 0
step-xv) assign start+len - 1 to end
step-xvi)if character at start and end are equal and dp[start+1][end-1] equal to 1 go to next step
step-xvii)assign 1 to dp[start][end] and insert substring from start to end as key and true as value in hashmap
step-xviii)else assign 0 to dp[start][end]
step-xix)increment start by one value
step-xx)repeat steps form xvi to xx till start is less than or equal to string length - len
step-xxi)increment len by one value
step-xxii)repeat steps from xv to xxii till len is less than string length
step-xxiii) return the size of the hashmap
Time Complexity: O(n^2)
Space Complexity:O(n^2)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution