Two Characters HackerRank Solution

Two Characters HackerRank Solution
Source : https://www.hackerrank.com/challenges/two-characters

In this challenge, you will be given a string. You must remove characters until the string is made up of any two alternating characters. When you choose a character to remove, all instances of that character must be removed. Your goal is to create the longest string possible that contains just two alternating letters.

As an example, consider the string abaacdabd. If you delete the character a, you will be left with the string bcdbd. Now, removing the character c leaves you with a valid string bdbd having a length of 4. Removing either b or d at any point would not result in a valid string.

Given a string , convert it to the longest possible string made up only of alternating characters. Print the length of string on a new line. If no string can be formed, print instead.

Function Description

Complete the alternate function in the editor below. It should return an integer that denotes the longest string that can be formed, or if it cannot be done.

alternate has the following parameter(s):

• s: a string

Input Format

The first line contains a single integer denoting the length of .
The second line contains string .

Constraints

Output Format

Print a single integer denoting the maximum length of for the given ; if it is not possible to form string , print instead.

Sample Input

10
beabeefeab

Sample Output

5

Explanation

The characters present in are a, b, e, and f. This means that must consist of two of those characters and we must delete two others. Our choices for characters to leave are [a,b], [a,e], [a, f], [b, e], [b, f] and [e, f].

If we delete e and f, the resulting string is babab. This is a valid as there are only two distinct characters (a and b), and they are alternating within the string.

If we delete a and f, the resulting string is bebeeeb. This is not a valid string because there are consecutive e's present. Removing them would leave consecutive b's, so this fails to produce a valid string .

Other cases are solved similarly.

babab is the longest string we can create.

Source : https://www.hackerrank.com/challenges/two-characters

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	/*
	Time Complexity: O(n) with just 1 traversal of our String
	Space Complexity: O(1)
	There are approximately 26^2 possible combinations of alternating pairs of letters.
	Notice that this number remains constant and is not dependent on the length of our
	input String. This fact will help us achieve a linear O(n) runtime.
	We want to solve this problem with just 1 traversal of our String, so we solve all
	26^2 subproblems simultaneously. We use two int[26][26] arrays to keep track of the
	26^2 solutions.
	As we iterate through our String, we update our two int[26][26] arrays as follows:
	- int[26][26] letter ---> This array is used to keep track of which of the alternating
	characters we saw last. To achieve this, for the current character "ch", we update the
	corresponding row (26 entries) and column (26 entries) with the (ASCII) value of "ch".
	- int[26][26] count ----> if we find that no solution exists for a pair of characters
	(which happens when the characters don't alternate), we store -1 in this array.
	Otherwise, we store he current maximum length of "s" for the pair of characters.
	Our final answer is the maximum value in our "int[26][26] count" array.
	*/
	public class Solution {
	public static final int NUM_LETTERS = 26;
	public static void main(String[] args) {
	/* Save input */
	Scanner scan = new Scanner(System.in);
	int length = scan.nextInt();
	String str = scan.next();
	scan.close();
	/* Edge case */
	if (length <= 1) {
	System.out.println(0);
	return;
	}
	/* Create arrays representing the 26^2 subproblems */
	int [][] pair = new int[NUM_LETTERS][NUM_LETTERS];
	int [][] count = new int[NUM_LETTERS][NUM_LETTERS];
	for (int i = 0; i < length; i++) {
	char letter = str.charAt(i);
	int letterNum = letter - 'a';
	/* Update row */
	for (int col = 0; col < NUM_LETTERS; col++) {
	if (pair[letterNum][col] == letter) {
	count[letterNum][col] = -1;
	}
	if (count[letterNum][col] != -1) {
	pair[letterNum][col] = letter;
	count[letterNum][col]++;
	}
	}
	/* Update column */
	for (int row = 0; row < NUM_LETTERS; row++) {
	if (pair[row][letterNum] == letter) {
	count[row][letterNum] = -1;
	}
	if (count[row][letterNum] != -1) {
	pair[row][letterNum] = letter;
	count[row][letterNum]++;
	}
	}
	}
	/* Find max in "count" array */
	int max = 0;
	for (int row = 0; row < NUM_LETTERS; row++) {
	for (int col = 0; col < NUM_LETTERS; col++) {
	max = Math.max(max, count[row][col]);
	}
	}
	System.out.println(max);
	}
	}