Translate Numbers to Their English Phrases

Problem Statement:
                    Write a program that takes an integer between 0-99,999 as input and output its English phrase.
For example :

             Input: 77890
             Output: Seventy Seven Thousand, Eight Hundred, and Ninety

Breaking down the problem:
              Such programs are commonly used in NLP to communicate with a user. They rarely use complex data structures or the programs are rarely complicated by themselves. They mostly are a chain of if-else conditions that handle particular cases. However, the sharpness of the programmer is tested here in the sense that he/she should handle all the possible inputs.

              If one observes above output, the commas and the word "and" are not associated with any digit in the number. However, according to the problem statement, they are very important. Such elements of the program, which need to be added for the sake of making the output "look better" or "closer to English" are often the main hurdles.
             
              Hence, there are 2 main sub-problems here. The first is to interpret the digits and convert them into their English words (taking care of their place in the number like the unnits place, tens place, etc.) and second is to take into account all the commas and the word "and" along with their placement.

Approach:
              The main hint here is the range of inputs - from 0 to 99,999. If one observes carefully, the last two digits and the first two digits always make one phrase in English. In the above input, the last digits "90" form Ninety and the first two digits "77" form Seventy Seven (along with thousand - their place value, but thats easy to predict). Hence, these will be considered in pairs. The third digit i.e. the digit in the hundred's place, is always alone. There is always a "Seven Hundred" or a "Three Hundred". There is never a "Seventy Three Hundred". Hence, logically, this is to be considered alone.

               Our first step should be to teach our program the English words, starting with the basics. The program needs to know that 0 becomes "Zero" and 1 becomes "One" and so on. Additionally, it also needs to know that 2 in tens place (or in the higher position whenever pairs are considered by the above logic) becomes "Twenty", 3 in similar position becomes "Thirty" and so on.

                English is a funny language. It is widely regarded as the toughest language for a program to learn, because of its sudden and seemingly illogical variations. For example, 11 has to become "Eleven" and not "Onety One". There is no reason why it cannot be "Onety One" for the sake of symmetry. But, such is life, and hence our program has to now learn about the phrases for the numbers from 11-19.

Trivia: The oldest Indian language, Sanskrit, is widely regarded as the easiest language for a program to learn owing to its symmetry.

                The next step is to implement the above approach. This is easy enough to do with a nested if-else tree. However, identifying the boundary conditions and all the cases and accomodating them was a pain to the author himself. For example, it is easy to overlook a small flaw in the above approach. If we take digits in pairs and check for words for them in an array, it becomes difficult for numbers with 0 as the lower number. For example, 77 becomes "Seventy Seven" by 70 is just "Seventy" and not "Seventy Zero". Hence, we need to make the 0th index of our array "unitsPlace" as an empty string. However, another issue now arises - how to handle if the input itself is just 0? This can be handles by adding yet another condition which checks if the input is 0, if it is - it simply prints "Zero" and exits. Any other 0s that might come will be translated to the null string.

                  The final step for ", and" is added to check if a phrase is not left hanging with those words as its last. There needs to be some word after "and" or else the program has some error.

Run Length Encoding

INPUT :
A string "s" consisting of possibly repeating characters. 
E.g. "aaaaabbbcddddefgttt"

OUTPUT :
A string s' such that s'.length() <= s.length(). String shortening is done by counting the contiguous occurrence of the characters and replacing them by the single character and its count of occurrence.
E.g. "a5b3cd4efgt3" 

Wikipedia Page

Number Of Occurences Of A Word In A Sentence

INPUT: A sentence containing one or many words like "Hello World Hello Java". We assume that no punctuation marks have been used.

OUTPUT: The number of occurenes of each word. For example, in the above example, the output we get is:
Hello - 2
World - 1
Java - 1
Note that the words "Hello" and "hello" are not the same i.e. the words are case-sensitive

BRUTE FORCE METHOD:
The first step is to break the sentence into words. We then store the words in an ArrayList for ease.

The brute force method is obviously to compare every word in the sentence with every other word. This will take ϴ(n²) for a n-worded sentence as it will involve 2 nested for-loops and every possible pair will be checked.

HASH-MAP IMPLEMENTATION:
In this approach, the first step remains the same - to break the sentence up ino words and arrange the in an ArrayList. Note that this step costs ϴ(n) as 1 full traversal of the array is needed.

However, we now count the number of occurences using Hash-Map instead. We create a HashMap named "map" which has the ASCII value of each word as its key and the word itself as its value. We then iterate over this HashMap and print count of each word. To store count, we either implement another HashMap or a set of variables.

Note that the above step finds the number of occurences in O(n) time. The worst case will be achieved when each word is distinct in the sentence. Thus, at the cost of O(n) extra memory, we reduced the ime-complexity of the programme from ϴ(n²) to O(n).

Longest Palindrome In The String

INPUT :
A string of length n.

OUTPUT :
A palindromic string which is the longest sub-string of the inputted string. Thus the output string can have a maximum length of 'n'

THE BRUTE FORCE METHOD :
Since we are looking for a sub-string, the brute force method would suggest finding every possible sub-string in the string and checking if its a palindrome. The algorithm to find every sub-string accepts the inputted string 's' and its length 'n' as parameters. We assume the existence of a pseudo function isPalindrome which accepts a string as parameter and returns true if the string is a palindrome and false otherwise. We also assume subString(String, startIndex, endIndex) to be a function that returns the substring of s beginning from startIndex (including) and ending at endIndex (excluding). This is quite similar to the Java.lang.String.substring(int beginIndex, int endIndex). The algorithm uses 3 variables : maxlen to find out the maximum length of the palindrome, templen to compare with maxlen, start and end as the begin and end indices of the palindrome respectively.

Algorithm findSubString (String s)

1. maxlen = 0 ,  templen = 0, start = 0, end = 0
2. for (int i = 0 up to n-1) 
3.      for (int j = i down to 0)
4.            for (int k = i+1 up to n)
5.                          templen = k-j+1
6.                          if ( isPalindrome(subString(s, j, k+1)) && templen > maxlen) 
7.                               maxlen = templen
8.                               start = j
9.                               end = k+1 // k+1 is because subString excludes the endIndex
10.                          end if
11.               end for
12.         end for
13. end for
14. return subString(s, start, end)

However, as we see, this approach uses 3 traversals in 3 nested for loops, taking O(n³) time. It should be noted that the time-efficiency of the function isPalindrome() is not taken into consideration as it is, anyways, less than O(n³) (shall be proved in a few moments).

THE isPalindrome() FUNCTION :
The most efficient method of determining whether a string is palindrome or no is to start with its central character and to go one character each to the left and right simultaneously checking whether the string is a palindrome. For example, for "abcba", we start at "c", which is the central character and then go one character to the left getting "b" and one character to the right getting "b" again. Thus "bcb" is a palindrome. We go on doing this till the string stops being a palindrome. This is essentially the algorithm behind isPalindrome(). Let us say that we divide every palindromic string of length, say p, into 2 kinds : when p is even and when p is odd. 

1.  when p is odd, as in "abcba", we fix 1 mid-point (here "c"), then compare every character at an "x" distance from it to the left to every character at the same distance from it to the right.
2. when p is even, like "abccba", we fix no mid-point, and begin comparing from "c" and "c" (they occupy the center positions in the string; 6/2 = 3 therefore 3rd and 4th positions are central) and then continue as above.

Thus we see, that any string can be checked for palindrome in O(n) times (1 traversal).

A BETTER APPROACH :
Note that we need to find a palindromic sub-string. Such a sub-string may begin or end at any index in the string, and not necessarily at the beginning and the end of the string. For example, for "banana", the longest palindromic sub-string is "anana" which doesn't start at the beginning of the string. So to speak, we do not know the start or the end of the sub-string and thus we cannot find the mid-point. Hence, we need to consider every character as the mid-point and begin checking for the palindromes. This will take 1 traversal of the string. A java code implementing this approach is as follows :

Do leave any comments if you find a better approach or if you have any doubts regarding the given approach. 

Courtesy : http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/