Project 2
- Arrays and Strings
SUBARRAY WITH GIVEN SUM
public class SubarraySum {
/* Returns true if the there is a
subarray of arr[] with a sum equal to
'sum' otherwise returns false.
Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
System.out.println("Sum found at indexe "
+ i);
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
System.out.println(
"Sum found between indexes " + i
+ " and " + j);
return;
}
}
}
}
System.out.println("No subarray found");
return;
}
public static void main(String[] args)
{
SubarraySum arraysum = new SubarraySum();
int arr[] = { 1, 2, 3, 7, 5, 12 };
int n = arr.length;
int sum = 12;
arraysum.subArraySum(arr, n, sum);
}
}
output;
Sum found between indexes 1 and 3---------------------------------------------------------------------------------
PERMUTATIONS OF A GIVEN STRING
// Java program to print all permutations of a
// given string.
public class Permutation {
// Function call
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Permutation permutation = new Permutation();
permutation.permute(str, 0, n - 1);
}
/**
* permutation function
* @param str string to calculate permutation for
* @param l starting index
* @param r end index
*/
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else {
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
permute(str, l + 1, r);
str = swap(str, l, i);
}
}
}
/**
* Swap Characters at position
* @param a string value
* @param i position 1
* @param j position 2
* @return swapped string
*/
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
output;
ABC
ACB
BAC
BCA
CBA
CAB
------------------------------------------------------------------------
DETERMINE IF TWO TREES ARE IDENTICAL
class Node {
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree {
Node root1, root2;
/* Given two trees, return true if they are
structurally identical */
boolean identicalTrees(Node a, Node b)
{
/*1. both empty */
if (a == null && b == null)
return true;
/* 2. both non-empty -> compare them */
if (a != null && b != null)
return (a.data == b.data
&& identicalTrees(a.left, b.left)
&& identicalTrees(a.right, b.right));
/* 3. one empty, one not -> false */
return false;
}
/* Driver code*/
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root1 = new Node(1);
tree.root1.left = new Node(7);
tree.root1.right = new Node(8);
tree.root1.left.left = new Node(9);
tree.root2 = new Node(1);
tree.root2.left = new Node(7);
tree.root2.right = new Node(8);
tree.root2.left.left = new Node(9);
// Function call
if (tree.identicalTrees(tree.root1, tree.root2))
System.out.println("Both trees are identical");
else
System.out.println("Trees are not identical");
}
}
output;
Both trees are identical------------------------------------------------------------------------------
COUNT LEAVES IN BINARY TREE
package Test_1;
//Java implementation to find leaf count of a given Binary tree
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
//Root of the Binary Tree
Node root;
/* Function to get the count of leaf nodes in a binary tree*/
int getLeafCount()
{
return getLeafCount(root);
}
int getLeafCount(Node node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
else
return getLeafCount(node.left) + getLeafCount(node.right);
}
/* Driver program to test above functions */
public static void main(String args[])
{
/* create a tree */
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(5);
tree.root.right = new Node(10);
tree.root.left.left = new Node(39);
/* get leaf count of the abve tree */
System.out.println("The leaf count of binary tree is : "
+ tree.getLeafCount());
}
}
output;
The leaf count of binary tree is : 2--------------------------------------------------------------------------------
COUNT LEAVES IN BINARY TREE
package Test_1;
//Java implementation to find leaf count of a given Binary tree
/* Class containing left and right child of current
node and key value*/
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
//Root of the Binary Tree
Node root;
/* Function to get the count of leaf nodes in a binary tree*/
int getLeafCount()
{
return getLeafCount(root);
}
int getLeafCount(Node node)
{
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
else
return getLeafCount(node.left) + getLeafCount(node.right);
}
/* Driver program to test above functions */
public static void main(String args[])
{
/* create a tree */
BinaryTree tree = new BinaryTree();
tree.root = new Node(4);
tree.root.left = new Node(8);
tree.root.right = new Node(10);
tree.root.left.left = new Node(7);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(1);
tree.root.right.right.left = new Node(3);
/* get leaf count of the abve tree */
System.out.println("The leaf count of binary tree is : "
+ tree.getLeafCount());
}
}
output;
The leaf count of binary tree is : 3------------------------------------------------------------------------------
LOWEST COMMON ANCESTOR IN A BINARY TREE
//Java implementation to find lowest common ancestor of
//n1 and n2 using one traversal of binary tree
/* Class containing left and right child of current
node and key value*/
class Node {
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree {
// Root of the Binary Tree
Node root;
Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}
// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA(Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;
// If either n1 or n2 matches with root's key,
// report the presence by returning root (Note that
// if a key is ancestor of other, then the ancestor
// key becomes LCA
if (node.data == n1 || node.data == n2)
return node;
// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);
// If both of the above calls return Non-NULL, then
// one key is present in once subtree and other is
// present in other, So this node is the LCA
if (left_lca != null && right_lca != null)
return node;
// Otherwise check if left subtree or right subtree
// is LCA
return (left_lca != null) ? left_lca : right_lca;
}
/* Driver program to test above functions */
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
System.out.println("LCA(1, 2) = "
+ tree.findLCA(1, 2).data);
}
}
output;
LCA(1, 2) = 1--------------------------------------------------------------------------------
LINKED LIST OF 0S, 1S AND 2S, SORT IT.
class Node
{
int data;
Node next;
Node(int data)
{
this.data=data;
}
}
class SortIt
{
public static Node sortList(Node head)
{
if(head==null || head.next==null)
{
return head;
}
Node zeroD = new Node(0);
Node oneD = new Node(0);
Node twoD = new Node(0);
Node zero = zeroD, one = oneD, two = twoD;
Node curr = head;
while (curr!=null)
{
if (curr.data == 0)
{
zero.next = curr;
zero = zero.next;
curr = curr.next;
}
else if (curr.data == 1)
{
one.next = curr;
one = one.next;
curr = curr.next;
}
else
{
two.next = curr;
two = two.next;
curr = curr.next;
}
}
zero.next = (oneD.next!=null)? (oneD.next) : (twoD.next);
one.next = twoD.next;
two.next = null;
head = zeroD.next;
return head;
}
// function to create and return a node
public static Node newNode(int data)
{
// allocating space
Node newNode = new Node(data);
newNode.next = null;
return newNode;
}
/* Function to print linked list */
public static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data+" ");
node = node.next;
}
}
public static void main(String args[])
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(2);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(2);
head.next.next.next.next.next = new Node(0);
head.next.next.next.next.next.next = new Node(2);
head.next.next.next.next.next.next.next = new Node(2);
System.out.println("Linked List Before Sorting");
printList(head);
head = sortList(head);
System.out.println("Linked List After Sorting");
printList(head);
}
output;
Linked List Before Sorting1 2 2 1 2 0 2 2 Linked List After Sorting
0 1 1 2 2 2 2 2-------------------------------------------------------------------
FIND FIRST REPEATED CHARACTER
// Java program to find the first
// repeated character in a string
import java.util.*;
class Main
{
// This function prints the first repeated
// character in str[]
static char firstRepeating(char str[])
{
// Creates an empty hashset
HashSet h = new HashSet<>();
// Traverse the input array from left to right
for (int i=0; i<=str.length-1; i++)
{
char c = str[i];
// If element is already in hash set, update x
// and then break
if (h.contains(c))
return c;
else // Else add element to hash set
h.add(c);
}
return '\0';
}
// Driver method to test above method
public static void main (String[] args)
{
String str = "Skilllync";
char[] arr = str.toCharArray();
System.out.println(firstRepeating(arr));
}
}
output;
1----------------------------------------------------------------------------------
CHECK IF TWO ARRAYS ARE EQUAL OR NOT
// Java program to find given two array
// are equal or not
import java.io.*;
import java.util.*;
class Main {
// Returns true if arr1[0..n-1] and
// arr2[0..m-1] contain same elements.
public static boolean areEqual(int arr1[], int arr2[])
{
int N = arr1.length;
int M = arr2.length;
// If lengths of array are not equal means
// array are not equal
if (N != M)
return false;
// Sort both arrays
Arrays.sort(arr1);
Arrays.sort(arr2);
// Linearly compare elements
for (int i = 0; i < N; i++)
if (arr1[i] != arr2[i])
return false;
// If all elements were same.
return true;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 1, 2, 5 };
int arr2[] = { 2, 4,15,};
// Function call
if (areEqual(arr1, arr2))
System.out.println("1");
else
System.out.println("0");
}
}
output;
0-------------------------------------------------------------------------------------------
RELATIVE SORTING
// A JAVA program to sort an array according
// to the order defined by another array
import java.io.*;
import java.util.Arrays;
class Main {
/* A Binary Search based function to find
index of FIRST occurrence of x in arr[].
If x is not present, then it returns -1 */
static int first(int arr[], int low, int high, int x,
int n)
{
if (high >= low) {
/* (low + high)/2; */
int mid = low + (high - low) / 2;
if ((mid == 0 || x > arr[mid - 1])
&& arr[mid] == x)
return mid;
if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
return first(arr, low, (mid - 1), x, n);
}
return -1;
}
// Sort A1[0..m-1] according to the order
// defined by A2[0..n-1].
static void sortAccording(int A1[], int A2[], int m,
int n)
{
// The temp array is used to store a copy
// of A1[] and visited[] is used to mark the
// visited elements in temp[].
int temp[] = new int[m], visited[] = new int[m];
for (int i = 0; i < m; i++) {
temp[i] = A1[i];
visited[i] = 0;
}
// Sort elements in temp
Arrays.sort(temp);
// for index of output which is sorted A1[]
int ind = 0;
// Consider all elements of A2[], find them
// in temp[] and copy to A1[] in order.
for (int i = 0; i < n; i++) {
// Find index of the first occurrence
// of A2[i] in temp
int f = first(temp, 0, m - 1, A2[i], m);
// If not present, no need to proceed
if (f == -1)
continue;
// Copy all occurrences of A2[i] to A1[]
for (int j = f; (j < m && temp[j] == A2[i]);
j++) {
A1[ind++] = temp[j];
visited[j] = 1;
}
}
// Now copy all items of temp[] which are
// not present in A2[]
for (int i = 0; i < m; i++)
if (visited[i] == 0)
A1[ind++] = temp[i];
}
// Utility function to print an array
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program to test above function.
public static void main(String args[])
{
int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };
int A2[] = { 2, 1, 8, 3 };
int m = A1.length;
int n = A2.length;
System.out.println("Sorted array is ");
sortAccording(A1, A2, m, n);
printArray(A1, m);
}
}
output;
Sorted array is 2 2 1 1 8 8 3 5 6 7 9 ---------------------------------------------------------------------------
SHORTEST SOURCE TO DESTINATION PATH
// Java program to find if there is path
// from top left to right bottom
import java.io.*;
import java.util.*;
class pair {
int Item1, Item2;
pair(int f, int s)
{
Item1 = f;
Item2 = s;
}
}
class GFG {
static int row = 3;
static int col = 4;
// To find the path from
// top left to bottom right
static boolean isPath(int[][] arr)
{
// Directions
int[][] dir
= { { 2, 3 } };
// Queue
Queue q = new LinkedList<>();
// Insert the top right corner.
q.add(new pair(0, 0));
// Until queue is empty
while (q.size() > 0) {
pair p = (q.peek());
q.remove();
// Mark as visited
arr[p.Item1][p.Item2] = -1;
// Destination is reached.
if (p.Item1 == row - 1 && p.Item2 == col - 1)
return true;
// Check all four directions
for (int i = 0; i < 4; i++) {
// Using the direction array
int a = p.Item1 + dir[i][0];
int b = p.Item2 + dir[i][1];
// Not blocked and valid
if (a >= 0 && b >= 0 && a < row && b < col
&& arr[a][b] != -1) {
if (a == row - 1 && b == col - 1)
return true;
q.add(new pair(a, b));
}
}
}
return false;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[][] arr = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 1, 1 } };
// Path from arr[0][0] to arr[row][col]
if (isPath(arr))
System.out.println("5");
else
System.out.println("3");
}
}
output;
5 ------------------------------------------------------------------------------------
MINIMUM COST PATH
// Java program to get least cost path
// in a grid from top-left to bottom-right
import java.io.*;
import java.util.*;
class CostPath{
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static int ROW = 5;
static int COL = 5;
// Custom class for representing
// row-index, column-index &
// distance of each cell
static class Cell
{
int x;
int y;
int distance;
Cell(int x, int y, int distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
}
// Custom comparator for inserting cells
// into Priority Queue
static class distanceComparator
implements Comparator
{
public int compare(Cell a, Cell b)
{
if (a.distance < b.distance)
{
return -1;
}
else if (a.distance > b.distance)
{
return 1;
}
else {return 0;}
}
}
// Utility method to check whether current
// cell is inside grid or not
static boolean isInsideGrid(int i, int j)
{
return (i >= 0 && i < ROW &&
j >= 0 && j < COL);
}
// Method to return shortest path from
// top-corner to bottom-corner in 2D grid
static int shortestPath(int[][] grid, int row,
int col)
{
int[][] dist = new int[row][col];
// Initializing distance array by INT_MAX
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
dist[i][j] = Integer.MAX_VALUE;
}
}
// Initialized source distance as
// initial grid position value
dist[0][0] = grid[0][0];
PriorityQueue pq = new PriorityQueue(
row * col, new distanceComparator());
// Insert source cell to priority queue
pq.add(new Cell(0, 0, dist[0][0]));
while (!pq.isEmpty())
{
Cell curr = pq.poll();
for(int i = 0; i < 4; i++)
{
int rows = curr.x + dx[i];
int cols = curr.y + dy[i];
if (isInsideGrid(rows, cols))
{
if (dist[rows][cols] >
dist[curr.x][curr.y] +
grid[rows][cols])
{
// If Cell is already been reached once,
// remove it from priority queue
if (dist[rows][cols] != Integer.MAX_VALUE)
{
Cell adj = new Cell(rows, cols,
dist[rows][cols]);
pq.remove(adj);
}
// Insert cell with updated distance
dist[rows][cols] = dist[curr.x][curr.y] +
grid[rows][cols];
pq.add(new Cell(rows, cols,
dist[rows][cols]));
}
}
}
}
return dist[row - 1][col - 1];
}
// Driver code
public static void main(String[] args)
throws IOException
{
int[][] grid = { { 31, 100, 65, 12, 18 },
{ 10, 13, 47, 157, 6 },
{ 100, 113, 174, 11, 33 },
{ 88, 124, 41, 20, 140 },
{ 99, 32, 111, 41, 20 } };
System.out.println(shortestPath(grid, ROW, COL));
}
}
output;
327---------------------------------------------------------------------------------
CIRCLE OF STRINGS
// Java program to check if a given
// directed graph is Eulerian or not
import java.util.ArrayList;
import java.util.List;
// A class that represents an
// undirected graph
class Main{
static final int CHARS = 26;
// No. of vertices
int V;
// A dynamic array of adjacency lists
List> adj;
int[] in;
// Constructor
Main(int V)
{
this.V = V;
in = new int[V];
adj = new ArrayList<>(CHARS);
for(int i = 0; i < CHARS; i++)
{
adj.add(i, new ArrayList<>());
}
}
// Function to add an edge to graph
void addEdge(int v, int w)
{
adj.get(v).add(w);
in[w]++;
}
// Method to check if this graph
// is Eulerian or not
boolean isEulerianCycle()
{
// Check if all non-zero degree
// vertices are connected
if (!isSC())
return false;
// Check if in degree and out
// degree of every vertex is same
for(int i = 0; i < V; i++)
if (adj.get(i).size() != in[i])
return false;
return true;
}
// This function returns true if all
// non-zero degree vertices of graph
// are strongly connected. Please refer
boolean isSC()
{
// Mark all the vertices as not
// visited (For first DFS)
boolean[] visited = new boolean[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Find the first vertex with
// non-zero degree
int n;
for(n = 0; n < V; n++)
if (adj.get(n).size() > 0)
break;
// Do DFS traversal starting from
// first non zero degree vertex.
DFSUtil(n, visited);
// If DFS traversal doesn't visit all
// vertices, then return false.
for(int i = 0; i < V; i++)
if (adj.get(i).size() > 0 && !visited[i])
return false;
// Create a reversed graph
Main gr = getTranspose();
// Mark all the vertices as not
// visited (For second DFS)
for(int i = 0; i < V; i++)
visited[i] = false;
// Do DFS for reversed graph starting
// from first vertex. Starting Vertex
// must be same starting point of first DFS
gr.DFSUtil(n, visited);
// If all vertices are not visited in
// second DFS, then return false
for(int i = 0; i < V; i++)
if (adj.get(i).size() > 0 && !visited[i])
return false;
return true;
}
// Function to do DFS starting from v.
// Used in isConnected();
// A recursive function to do DFS
// starting from v
void DFSUtil(int v, boolean[] visited)
{
// Mark the current node as
// visited and print it
visited[v] = true;
// Recur for all the vertices
// adjacent to this vertex
for(Integer i : adj.get(v))
if (!visited[i])
{
DFSUtil(i, visited);
}
}
// Function that returns reverse
// (or transpose) of this graph
// This function is needed in isSC()
Main getTranspose()
{
Main g = new Main(V);
for(int v = 0; v < V; v++)
{
// Recur for all the vertices
// adjacent to this vertex
for(Integer i : adj.get(v))
{
g.adj.get(i).add(v);
g.in[v]++;
}
}
return g;
}
// This function takes an of strings
// and returns true if the given array
// of strings can be chained to form cycle
static boolean canBeChained(String[] arr, int n)
{
// Create a graph with 'alpha' edges
Main g = new Main(CHARS);
// Create an edge from first character
// to last character of every string
for(int i = 0; i < n; i++)
{
String s = arr[i];
g.addEdge(s.charAt(0) - 'a',
s.charAt(s.length() - 1) - 'a');
}
// The given array of strings can be
// chained if there is an eulerian
// cycle in the created graph
return g.isEulerianCycle();
}
// Driver code
public static void main(String[] args) throws Exception
{
String[] arr1 = { "abc", "bcd",
"cdf" };
int n1 = arr1.length;
System.out.println((canBeChained(arr1, n1) ?
"1 " :
"0 "));
}
}
output;
0 -------------------------------------------------------------------------------------------------
FIRST NON-REPEATING CHARACTER IN A STREAM
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static String firstNonRepeatingCharacter(String str) {
StringBuilder resultantString = new StringBuilder();
int[] characterFrequency = new int[26];
// queue to store the characters
Queue queue = new LinkedList();
// traverse whole stream of characters
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
// push the character into the queue
queue.add(ch);
// increment the frequency count
characterFrequency[ch - 'a']++;
// check for the non repeating character
while (!queue.isEmpty()) {
// when the character is repeated
if (characterFrequency[queue.peek() - 'a'] > 1)
queue.remove();
// when the character is not repeating
else {
resultantString.append(queue.peek() + " ");
break;
}
}
// if there is no non-repeating character
if (queue.isEmpty())
resultantString.append("-1 ");
}
return resultantString.toString();
}
public static void main(String[] args) {
String str = "aabc";
String result = firstNonRepeatingCharacter(str);
System.out.println(result);
}
}
output;
a -1 b b --------------------------------------------------------------------------------------
REARRANGE CHARACTERS
// Java program to rearrange characters in a string
// so that no two adjacent characters are same.
import java.io.*;
import java.util.*;
class KeyComparator implements Comparator {
// Overriding compare()method of Comparator
public int compare(Key k1, Key k2)
{
if (k1.freq < k2.freq)
return 1;
else if (k1.freq > k2.freq)
return -1;
return 0;
}
}
class Key {
int freq; // store frequency of character
char ch;
Key(int val, char c)
{
freq = val;
ch = c;
}
}
class GFG {
static int MAX_CHAR = 26;
// Function to rearrange character of a string
// so that no char repeat twice
static void rearrangeString(String str)
{
int n = str.length();
// Store frequencies of all characters in string
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++)
count[str.charAt(i) - 'a']++;
// Insert all characters with their
// frequencies into a priority_queue
PriorityQueue pq
= new PriorityQueue<>(new KeyComparator());
for (char c = 'a'; c <= 'z'; c++) {
int val = c - 'a';
if (count[val] > 0)
pq.add(new Key(count[val], c));
}
// 'str' that will store resultant value
str = "";
// work as the previous visited element
// initial previous element be. ( '#' and
// it's frequency '-1' )
Key prev = new Key(-1, '#');
// traverse queue
while (pq.size() != 0) {
// pop top element from queue and
// add it to string.
Key k = pq.peek();
pq.poll();
str = str + k.ch;
// If frequency of previous character
// is less than zero that means it is
// useless, we need not to push it
if (prev.freq > 0)
pq.add(prev);
// make current character as the previous
// 'char' decrease frequency by 'one'
(k.freq)--;
prev = k;
}
// If length of the resultant string
// and original string is not same then
// string is not valid
if (n != str.length())
System.out.println("0 ");
else
System.out.println("1");
}
// Driver's code
public static void main(String args[])
{
String str = "bbbabaaacd";
// Function call
rearrangeString(str);
}
}
output;
1----------------------------------------------------------------------------------
LONGEST COMMON SUBSEQUENCE
/* A Naive recursive implementation of LCS problem in java*/
public class LongestCommonSubsequence
{
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char[] X, char[] Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b)? a : b;
}
public static void main(String[] args)
{
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
String s1 = "ABCBDAB";
String s2 = "BDCABA";
char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("the LCS(X, Y) =" + " " +
lcs.lcs( X, Y, m, n ) );
}
}
output;
the LCS(X, Y) = 4----------------------------------------------------------------------------
MAXIMUM SUM OF INCREASING SUBSEQUENCES
/* Dynamic Programming Java
implementation of Maximum Sum
Increasing Subsequence (MSIS)
problem */
class Subsequences
{
/* maxSumIS() returns the
maximum sum of increasing
subsequence in arr[] of size n */
static int maxSumIS(int arr[], int n)
{
int i, j, max = 0;
int msis[] = new int[n];
/* Initialize msis values
for all indexes */
for (i = 0; i < n; i++)
msis[i] = arr[i];
/* Compute maximum sum values
in bottom up manner */
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] &&
msis[i] < msis[j] + arr[i])
msis[i] = msis[j] + arr[i];
/* Pick maximum of all
msis values */
for (i = 0; i < n; i++)
if (max < msis[i])
max = msis[i];
return max;
}
// Driver code
public static void main(String args[])
{
int arr[] = new int[]{1, 101, 2, 3, 100, 4, 5};
int n = arr.length;
System.out.println("Sum of maximum sum "+
"increasing subsequence is "+
maxSumIS(arr, n));
}
}
output;
Sum of maximum sum increasing subsequence is 106------------------------------------------------------------------------------
COUNT NUMBER OF HOPS
package Test_1;
//A Dynamic Programming based Java program
//to count number of ways to cover a distance
//with 1, 2 and 3 steps
import java.io.*;
public class main
{
// Function returns count of ways to cover 'dist'
static int printCountDP(int dist)
{
int[] count = new int[dist+1];
// Initialize base values. There is one way to
// cover 0 and 1 distances and two ways to
// cover 2 distance
count[0] = 1;
if(dist >= 1)
count[1] = 1;
if(dist >= 2)
count[2] = 2;
// Fill the count array in bottom up manner
for (int i=3; i<=dist; i++)
count[i] = count[i-1] + count[i-2] + count[i-3];
return count[dist];
}
// driver program
public static void main (String[] args)
{
int dist = 5;
System.out.println(printCountDP(dist));
}
}
output;
13-----------------------------------------------------------------------------------------------
N MEETINGS IN ONE ROOM
// Java program to find maximum number of meetings
import java.util.*;
// Comparator function which can compare
// the ending time of the meeting ans
// sort the list
class mycomparator implements Comparator {
@Override public int compare(meeting o1, meeting o2)
{
if (o1.end < o2.end) {
// Return -1 if second object is
// bigger then first
return -1;
}
else if (o1.end > o2.end)
// Return 1 if second object is
// smaller then first
return 1;
return 0;
}
}
// Custom class for storing starting time,
// finishing time and position of meeting.
class meeting {
int start;
int end;
int pos;
meeting(int start, int end, int pos)
{
this.start = start;
this.end = end;
this.pos = pos;
}
}
class GFG {
// Function for finding maximum meeting in one room
public static void maxMeeting(ArrayList al,
int s)
{
// Initialising an arraylist for storing answer
ArrayList m = new ArrayList<>();
int time_limit = 0;
mycomparator mc = new mycomparator();
// Sorting of meeting according to
// their finish time.
Collections.sort(al, mc);
// Initially select first meeting.
m.add(al.get(0).pos);
// time_limit to check whether new
// meeting can be conducted or not.
time_limit = al.get(0).end;
// Check for all meeting whether it
// can be selected or not.
for (int i = 1; i < al.size(); i++) {
if (al.get(i).start > time_limit) {
// Add selected meeting to arraylist
m.add(al.get(i).pos);
// Update time limit
time_limit = al.get(i).end;
}
}
// Print final selected meetings.
for (int i = 0; i < m.size(); i++)
System.out.print(m.get(i) + 1 + " ");
}
// Driver's Code
public static void main(String[] args)
{
// Starting time
int s[] = { 1, 3, 0, 5, 8, 5 };
// Finish time
int f[] = { 2, 4, 6, 7, 9, 9 };
// Defining an arraylist of meet type
ArrayList meet = new ArrayList<>();
for (int i = 0; i < s.length; i++)
// Creating object of meeting
// and adding in the list
meet.add(new meeting(s[i], f[i], i));
// Function call
maxMeeting(meet, meet.size());
}
}
output;
1 2 4 5
---------------------------------------------------------------------------------------
MINIMISE THE SUM OF PRODUCT
import java.io.*;
import java.util.*;
class Main {
// Returns minimum sum of product of two arrays
// with permutations allowed
static long minValue(int A[], int B[], int n)
{
// Sort A and B so that minimum and maximum
// value can easily be fetched.
Arrays.sort(A);
Arrays.sort(B);
// Multiplying minimum value of A
// and maximum value of B
long result = 0;
for (int i = 0; i < n; i++)
result += (A[i] * B[n - i - 1]);
return result;
}
// Driven Code
public static void main(String[] args)
{
int A[] = { 3, 1, 1 };
int B[] = { 6, 5, 4 };
int n = A.length;
;
System.out.println(minValue(A, B, n));
}
}
ouput;
23
----------------------------------------------------------------------------------
LARGEST NUMBER POSSIBLE
public class Main
{
// Function to print the largest possible number with digit sum 's'
// and 'm' number of digits
static void findLargest(int m, int s)
{
// If sum of digits is 0, then a number is possible
// only if number of digits is 1
if (s == 0)
{
System.out.print(m == 1 ? "Largest number is 0" : "Not possible");
return ;
}
// Sum greater than the maximum possible sum
if (s > 9*m)
{
System.out.println("Not possible");
return ;
}
// Create an array to store digits of result
int[] res = new int[m];
// Fill from most significant digit to least
// significant digit
for (int i=0; i= 9)
{
res[i] = 9;
s -= 9;
}
// If remaining sum becomes less than 9, then
// fill the remaining sum
else
{
res[i] = s;
s = 0;
}
}
System.out.print("Largest number is ");
for (int i=0; i --------------------------------------------------------------------------
LONGEST DISTINCT CHARACTERS IN STRING
import java.io.*;
import java.util.*;
public class Main{
// This function returns true if all characters in
// str[i..j] are distinct, otherwise returns false
public static Boolean areDistinct(String str,
int i, int j)
{
// Note : Default values in visited are false
boolean[] visited = new boolean[26];
for(int k = i; k <= j; k++)
{
if (visited[str.charAt(k) - 'a'] == true)
return false;
visited[str.charAt(k) - 'a'] = true;
}
return true;
}
// Returns length of the longest substring
// with all distinct characters.
public static int longestUniqueSubsttr(String str)
{
int n = str.length();
// Result
int res = 0;
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++)
if (areDistinct(str, i, j))
res = Math.max(res, j - i + 1);
return res;
}
// Driver code
public static void main(String[] args)
{
String str = "abababcdefababcdab";
System.out.println("The input string is " + str);
int len = longestUniqueSubsttr(str);
System.out.println("The length of the longest " +
"non-repeating character " +
"substring is " + len);
}
}
output;
The input string is abababcdefababcdabThe length of the longest non-repeating character substring is 6-----------------------------------------------------------------------------
SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING
// Java program to find smallest
// window containing
// all characters of a pattern.
public class Main {
static final int no_of_chars = 256;
// Function to find smallest
// window containing
// all characters of 'pat'
static String findSubString(String str, String pat)
{
int len1 = str.length();
int len2 = pat.length();
// Check if string's length is
// less than pattern's
// length. If yes then no such
// window can exist
if (len1 < len2) {
System.out.println("No such window exists");
return "";
}
int hash_pat[] = new int[no_of_chars];
int hash_str[] = new int[no_of_chars];
// Store occurrence ofs
// characters of pattern
for (int i = 0; i < len2; i++)
hash_pat[pat.charAt(i)]++;
int start = 0, start_index = -1,
min_len = Integer.MAX_VALUE;
// Start traversing the string
// Count of characters
int count = 0;
for (int j = 0; j < len1; j++) {
// Count occurrence of characters
// of string
hash_str[str.charAt(j)]++;
// If string's char matches
// with pattern's char
// then increment count
if (hash_str[str.charAt(j)]
<= hash_pat[str.charAt(j)])
count++;
// If all the characters are matched
if (count == len2) {
// Try to minimize the window
while (hash_str[str.charAt(start)]
> hash_pat[str.charAt(start)]
|| hash_pat[str.charAt(start)]
== 0) {
if (hash_str[str.charAt(start)]
> hash_pat[str.charAt(start)])
hash_str[str.charAt(start)]--;
start++;
}
// update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
// If no window found
if (start_index == -1) {
System.out.println("No such window exists");
return "";
}
// Return substring starting
// from start_index
// and length min_len
return str.substring(start_index,
start_index + min_len);
}
// Driver Method
public static void main(String[] args)
{
String str = "Timetopractice";
String pat = "toc";
System.out.print(findSubString(str, pat));
}
}
output;
toprac----------------------------------------------------------------------------------------------
POWER OF 2
import java.lang.Math;
public class Main {
/* Function to check if x is power of 2*/
static boolean isPowerOfTwo(int n)
{
if (n == 0)
return false;
return (int)(Math.ceil((Math.log(n) / Math.log(2))))
== (int)(Math.floor(
((Math.log(n) / Math.log(2)))));
}
// Driver Code
public static void main(String[] args)
{
// Function call
if (isPowerOfTwo(1))
System.out.println("Yes");
else
System.out.println("No");
if (isPowerOfTwo(98))
System.out.println("Yes");
else
System.out.println("No");
}
}
output;
yes
No------------------x-----------------