Code Destine

Problem Statement

You have given a ransom note string and a string consists of all of the letters of the magazine. Write a program to find out if a ransom note can be constructed from the magazine.

Each letter in the magazine string can only be used once in the ransom note.

Note:- Both strings contain only lowercase letters.

Example 

Input :- Ransom Note = "morning" , Magazine = "abcghimnoprsnab"
Output :- true

Input :- Ransom Note = "sun" , Magazine = "abcghimnoprsnab"
Output :- false

Solution

To solve this problem, we have to check, if all the characters of ransomNote string are present in the magazine string or not.

This problem can be solved in following steps :-

1. Create the character array from both the input String ransomNote and magazine.
2. Create an integer array (count array) of size 26 (Total number of characters in the English language), This array will be used to store the frequency of each character in the magazine string.
3. Traverse the magazine character array from start (index 0) to end (n-1, where n is the length of an array) and convert each character into an index of count array by subtracting the character from ‘a’ and converting it into ASCII code. Increase the count for the calculated index by 1.
4. Traverse the ransomNote character array from start (index 0) to end (n-1, where n is the length of an array) and convert each character into an index of count array i by subtracting the character from ‘a’ and converting it into ASCII code. If the value at index i is less than or equal to zero, then return false. Otherwise, decrease the value at index i by 1.
5. If traversal of ransomNote executes successfully, then returns true.

Program

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		boolean result = main.canConstruct("sun", "abcghimnoprsnab");
		System.out.println(result);
	}
	
	/* Solution */
	public boolean canConstruct(String ransomNote, String magazine) {
        
        char[] array = magazine.toCharArray();
        
        int[] countArray = new int[26];        
        for(char c : array){            
            countArray[c-'a']++;
        }
        
        array = ransomNote.toCharArray();
        for(char c : array){   
            if(countArray[c-'a'] > 0){
                countArray[c-'a']--;
            }else {
                return false;
            }            
        }
        return true;
    }
}

Result

true

Similar Post

1. Single Row Keyboard
2. Alphabet Board Path
3. Convert Roman Number to Decimal

That’s all for Ransom Note in Java, If you liked it, please share your thoughts in a comments section and share it with others too.