Project 2
SUBARRAY WITH GIVEN SUM
Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.
Implement a method subArraySum(a[], s), where A is array of size n and s is the sum.
And return the starting and ending positions (0 indexing) of FIRST such occurring subarray from the left if sum equals to subarray, else print -1.
Code knowing that-
1 <= N <= 107">107107
1 <= Ai <= 1010">1010
Explanation: we follow the following steps to solve this problem:
step 1: we will create a variable current sum and start. assign as 0 at this moment.
step 2: we will traverse the array from start to end
step 3: we will keep updating the sum, sum = sum + arr[i]
step 4: if the sum is greater than the given sum then we will update if as sum = sum - array[start] and update start as start++
step 5: and if the sum is equal to the give sum sum then we will break the loop and we'll print the sub array.
Code:
package project2;
public class SubArraySum {
int subArraySum(int arr[], int n, int sum)
{
int curr_sum = arr[0], start = 0, i;
// Pick a starting point
for (i = 1; i <= n; i++) {
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum > sum && start < i - 1) {
curr_sum = curr_sum - arr[start];
start++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum == sum) {
int p = i - 1;
System.out.println(
"Sum found between indexes " + start
+ " and " + p);
return 1;
}
// Add this element to curr_sum
if (i < n)
curr_sum = curr_sum + arr[i];
}
System.out.println("No subarray found");
return 0;
}
public static void main(String[] args)
{
SubArraySum arraysum = new SubArraySum();
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
//output:
//Sum found between indexes 1 and 4
Time Complexity: O(n)
Space Compelxity: O(1)Video: Link
-------------------------------------------------------
PERMUTATIONS OF A GIVEN STRING
Given a string S. The task is to print all permutations of a given string. Implement perm(s) method where s is a string in capital letter. Print all permutations of a given string S with single space and all permutations should be in lexicographically increasing order.
Constraints:
1 ≤ size of string ≤ 5
Explanation: To solve this problem we will use backtracking method where we will take the string value and will recursively call for each character after fixing each character and recursively calling for the rest of the character.
Code:
package project2;
public class PermutationString {
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);
}
}
}
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);
}
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
PermutationString permutation = new PermutationString();
permutation.permute(str, 0, n-1);
}
}
//Output: ABC ACB BAC BCA CBA CAB
//Time Complexity = O(n*n!)
//Space Complexity = O(r-l)Video: Link
------------------------------------------
DETERMINE IF TWO TREES ARE IDENTICAL
Given two binary trees, the task is to find if both of them are identical or not.
Complete the function isIdentical() that takes two roots as parameters and returns true or false.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).
Constraints:
1 <= Number of nodes <= 1000
1 <=Data of a node <= 1000
Explanation: To solve this problem we will take two binary tree and compare each node and return true if identical, and recursively call for the sub half of each and compare.
if both the trees are empty then return -1 or else we will compare the trees.
Code:
package project2;
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
public class BTreeIdentical {
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 program to test identicalTrees() function */
public static void main(String[] args)
{
BTreeIdentical tree = new BTreeIdentical();
tree.root1 = new Node(1);
tree.root1.left = new Node(2);
tree.root1.right = new Node(3);
tree.root1.left.left = new Node(4);
tree.root1.left.right = new Node(5);
tree.root2 = new Node(1);
tree.root2.left = new Node(2);
tree.root2.right = new Node(3);
tree.root2.left.left = new Node(4);
tree.root2.left.right = new Node(5);
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
//Time complexity: O(n)Video : Link
----------------------------------------
COUNT LEAVES IN BINARY TREE
For the above tree, the string will be: 5 2 3 1 N 7 4 N 8 N 6 N N Complete the function countLeaves() that takes the tree string as parameter and returns the count of leaves in tree.
Constraints:
1<= N <= 104">104
Explanation: To solve this problem we will follow the following steps:
step 1: if root is null then we will return 0
step 2: if if left and right child of the root is null then we will return 1
step3: else we will recursively traverse the node and count the leaf.
Code:
package project2;
public class CountLeafInTree {
//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 */
CountLeafInTree tree = new CountLeafInTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
/* get leaf count of the above tree */
System.out.println("The leaf count of binary tree is : "
+ tree.getLeafCount());
}
}
//output:
//The leaf count of binary tree is : 3
//Time complexity: O(n)Video: Link
---------------------------------------------------------
LOWEST COMMON ANCESTOR IN A BINARY TREE
Given a Binary Tree with all unique values and two nodes value n1 and n2. The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them is present.
Complete the function lca() that takes nodes, n1, and n2 as parameters and returns LCA node as output.
Expected Time Complexity: O(N).
Expected Space Complexity : O(H).
H is the height of the tree.
Constraints:
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000
Explanation:
We will create a function that will take a node and two value let say n1 and n2. later we will check if the current node value is less than n1 and n2 then we recursively call the right sub tree because the LCA is present on the right sub tree, and if the value of the current node is greater than n1 and n2 then we recursively call left sub tree because the LCA will be present on the left. if both this condition fails then we will say the current node is the LCA.
Keeping this logic in mind we will create a method LCA which will take node, int n1 and int n2 as the parameter, we'll write a if condition to check if node.data > n1 && node.data>n2 if this condition is true we will return LCA(node.left, n1, n2) because both the n1 and n2 are smaller than root.
we will declare a if bloack which will check if n1 and 2 are greater just the above if block and if the condition is satisfied we will return the recursive call to the LCA method with node.right as the parameter along with n1 and n2.
if both the condition fails we will just return the node.
Code:
package project2;
public class LowestCommonAncestor {
Node root;
/* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
Node lca(Node node, int n1, int n2)
{
if (node == null)
return null;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (node.data > n1 && node.data > n2)
return lca(node.left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (node.data < n1 && node.data < n2)
return lca(node.right, n1, n2);
return node;
}
/* Driver program to test lca() */
public static void main(String args[])
{
// Let us construct the BST shown in the above figure
LowestCommonAncestor tree = new LowestCommonAncestor();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
int n1 = 10, n2 = 14;
Node t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 14;
n2 = 8;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 10;
n2 = 22;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
}
}
//Output:
//LCA of 10 and 14 is 12
//LCA of 14 and 8 is 8
//LCA of 10 and 22 is 20
Time Complexity: O(n)
Space Complexity: O(h)
Video: Link
------------------------------------------------------
LINKED LIST OF 0S, 1S AND 2S, SORT IT.
Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.
complete the function segregate() which segregates the nodes in the linked list as asked in the problem statement and returns the head of the modified linked list. The printing is done automatically by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 103">103
Explanation: Tp solve this problem in O(n) time complexity we will traverse from the start of the linked list and will store the counter of 0's 1's and 2's.
Code:
package project2;
public class LLof123s {
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
void sortList()
{
// initialise count of 0 1 and 2 as 0
int count[] = {0, 0, 0};
Node ptr = head;
/* count total number of '0', '1' and '2'
* count[0] will store total number of '0's
* count[1] will store total number of '1's
* count[2] will store total number of '2's */
while (ptr != null)
{
count[ptr.data]++;
ptr = ptr.next;
}
int i = 0;
ptr = head;
/* Let say count[0] = n1, count[1] = n2 and count[2] = n3
* now start traversing list from head node,
* 1) fill the list with 0, till n1 > 0
* 2) fill the list with 1, till n2 > 0
* 3) fill the list with 2, till n3 > 0 */
while (ptr != null)
{
if (count[i] == 0)
i++;
else
{
ptr.data= i;
--count[i];
ptr = ptr.next;
}
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LLof123s llist = new LLof123s();
/* Constructed Linked List is 1->2->3->4->5->6->7->
8->8->9->null */
llist.push(0);
llist.push(1);
llist.push(0);
llist.push(2);
llist.push(1);
llist.push(1);
llist.push(2);
llist.push(1);
llist.push(2);
System.out.println("Linked List before sorting");
llist.printList();
llist.sortList();
System.out.println("Linked List after sorting");
llist.printList();
}
}
//Output:
//Linked List before sorting
//2 1 2 1 1 2 0 1 0
//Linked List after sorting
//0 0 1 1 1 1 2 2 2
Time Complexity: O(n)Video: Link
------------------------------------------------------------
FIND FIRST REPEATED CHARACTER
Given a string S. The task is to find the first repeated character in it. We need to find the character that occurs more than once and whose index of second occurrence is smallest.
S contains only lowercase letters.
Argument is a string S.
print the first repeating character in the string. If no such character exist print -1.
Constraints:
1 <= |S| <=104">104
Explanation: To solve this problem we will create a hash map to store the count of the character and will print the first repeating character.
step 1: Creating empty hash map
step 2: traversign through the entire string and inserting the count of the character inside hash map. when any character appears more then once we will increment the value of that character and return it.
Code:
package project2;
import java.util.HashSet;
public class RepeatedCharacter {
// 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 = "Looseeng";
char[] arr = str.toCharArray();
System.out.println(firstRepeating(arr));
}
}
//Output:
//o
//Time complexity: O(n)Video: Link
-----------------------------------------------
CHECK IF TWO ARRAYS ARE EQUAL OR NOT
Complete the function which takes two arrays A and B of equal size. Find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though. If there are repetitions, then counts of repeated elements must also be same for two array to be equal.
Print 1 if the arrays are equal else print 0.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 107">107107
1 <= A[],B[] <= 1018">1018
Explanation: To solve this problem we will use the hash map method.
step 1: Traverse the arr1[] and store it's the element and its count into the hash map
step 2: then we will traverse the arr2[] and check if the element is the same or not.
Code:
package project2;
import java.util.HashMap;
import java.util.Map;
public class CheckTwoArrayEqual {
public static boolean areEqual(int arr1[], int arr2[])
{
int n = arr1.length;
int m = arr2.length;
// If lengths of arrays are not equal
if (n != m)
return false;
// Store arr1[] elements and their counts in
// hash map
Map<Integer, Integer> map
= new HashMap<Integer, Integer>();
int count = 0;
for (int i = 0; i < n; i++) {
if (map.get(arr1[i]) == null)
map.put(arr1[i], 1);
else {
count = map.get(arr1[i]);
count++;
map.put(arr1[i], count);
}
}
// Traverse arr2[] elements and check if all
// elements of arr2[] are present same number
// of times or not.
for (int i = 0; i < n; i++) {
// If there is an element in arr2[], but
// not in arr1[]
if (!map.containsKey(arr2[i]))
return false;
// If an element of arr2[] appears more
// times than it appears in arr1[]
if (map.get(arr2[i]) == 0)
return false;
count = map.get(arr2[i]);
--count;
map.put(arr2[i], count);
}
return true;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 3, 5, 2, 5, 2 };
int arr2[] = { 2, 3, 5, 5, 2 };
if (areEqual(arr1, arr2))
System.out.println("Yes");
else
System.out.println("No");
}
}
//Output: yes
//Time Compelxity: O(n)
//Space Complexity: O(n)Video: Link
----------------------------------------
RELATIVE SORTING
Given two arrays A1[] and A2[] of size N and M respectively. The task is to sort A1 in such a way that the relative order among the elements will be same as those in A2. For the elements not present in A2, append them at last in sorted order. It is also given that the number of elements in A2[] are smaller than or equal to number of elements in A1[] andA2[] has all distinct elements.
Expected time complexity is O(N log(N)).
Length of arrays N and M and next two line contains N and M elements respectively.
Output:
Print the relatively sorted array.
Constraints:
1 ≤ A1[], A2[] <= 106">106
Explanation:
step 1: we will create a temp array to store the duplicate of arr1[]
step 2: Then we will create another visited array with 0 initially.
step 3: now we will sort the temp array
step 4: initially assign output index find as 0
step 5: now we will follow the following logic for each element in arr1[i] to arr2[]
a. Binary search for all occurrences of A2[i] in temp[], if present then copy all occurrences to A1[ind] and increment ind. Also mark the copied elements visited[]
step 6: copy all unvisited elements from temp to arr1[]
Code:
package project2;
import java.util.Arrays;
public class RelativeSorting {
/* 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
Time Complexity: O(nlogm)Video: Link
------------------------------------------------------------------
SHORTEST SOURCE TO DESTINATION PATH
Given a boolean 2D matrix (0-based index), find whether there is path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. You may move in only four direction ie up, down, left and right. The path can only be created out of a cell if its value is 1.
Complete the function for implementing this. Arguments are two integers n and m denoting the size of the matrix, an n*m matrix and two integers x and y denoting the index of the destination. Print the min no of steps needed to reach the destination.
Constraints:
1<=n,m<=20
Explanation:
Step 1: We start from the source cell and calls BFS procedure.
step 2: We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
step 3: We also maintain a Boolean array visited of same size as our input matrix and initialize all its elements to false.
a. We loop till queue is not empty
b. Dequeue front cell from the queue
c. Return if the destination coordinates have reached.
d. For each of its four adjacent cells, if the value is 1 and they are not visited yet, we enqueue it in the queue and also mark them as visited.
Code:
package project2;
import java.util.*;
public class ShortSourceDestination {
static int ROW = 9;
static int COL = 10;
// To store matrix cell coordinates
static class Point
{
int x;
int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
};
// A Data Structure for queue used in BFS
static class queueNode
{
Point pt; // The coordinates of a cell
int dist; // cell's distance of from the source
public queueNode(Point pt, int dist)
{
this.pt = pt;
this.dist = dist;
}
};
// check whether given cell (row, col)
// is a valid cell or not.
static boolean isValid(int row, int col)
{
// return true if row number and
// column number is in range
return (row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
static int rowNum[] = {-1, 0, 0, 1};
static int colNum[] = {0, -1, 1, 0};
// function to find the shortest path between
// a given source cell to a destination cell.
static int BFS(int mat[][], Point src,
Point dest)
{
// check source and destination cell
// of the matrix have value 1
if (mat[src.x][src.y] != 1 ||
mat[dest.x][dest.y] != 1)
return -1;
boolean [][]visited = new boolean[ROW][COL];
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
Queue q = new LinkedList<>();
// Distance of source cell is 0
queueNode s = new queueNode(src, 0);
q.add(s); // Enqueue source cell
// Do a BFS starting from source cell
while (!q.isEmpty())
{
queueNode curr = q.peek();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
// Otherwise dequeue the front cell
// in the queue and enqueue
// its adjacent cells
q.remove();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent cell is valid, has path
// and not visited yet, enqueue it.
if (isValid(row, col) &&
mat[row][col] == 1 &&
!visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] = true;
queueNode Adjcell = new queueNode
(new Point(row, col),
curr.dist + 1 );
q.add(Adjcell);
}
}
}
// Return -1 if destination cannot be reached
return -1;
}
// Driver Code
public static void main(String[] args)
{
int mat[][] = {{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }};
Point source = new Point(0, 0);
Point dest = new Point(3, 4);
int dist = BFS(mat, source, dest);
if (dist != -1)
System.out.println("Shortest Path is " + dist);
else
System.out.println("Shortest Path doesn't exist");
}
}
//output: Shortest Path is 11
Video: link
----------------------------------------------------------------
MINIMUM COST PATH
Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum. You can move in 4 directions : up, down, left an right. It is assumed that negative cost cycles do not exist in input matrix.
N denoting the size of the grid N*N integer matrix depicting the cost of respective cell from (0,0) to (N,N).
output a single integer depicting the minimum cost to reach the destination.
Constraints:
1 <= N <= 100
1 <= grid[i][j] <= 104
Explanation: the efficient method to solve this problem is explained below
We will create two for loops one for the column moment and the second for the first-row moment.
and lastly, we will create two nested for loops for the rest of the 2d matrix which will recursively call the same method and compare the shortest path using the Math.min method. this way we will get the final shortest distance.
Code:
package project2;
public class MinCostPath {
static int row = 3;
static int col = 3;
static int minCost(int cost[][])
{
// for 1st column
for (int i = 1; i < row; i++)
{
cost[i][0] += cost[i - 1][0];
}
// for 1st row
for (int j = 1; j < col; j++)
{
cost[0][j] += cost[0][j - 1];
}
// for rest of the 2d matrix
for (int i = 1; i < row; i++)
{
for (int j = 1; j < col; j++)
{
cost[i][j] += Math.min(cost[i - 1][j - 1],
Math.min(cost[i - 1][j],
cost[i][j - 1]));
}
}
// Returning the value in
// last cell
return cost[row - 1][col - 1];
}
// Driver code
public static void main(String[] args)
{
int cost[][] = {{1, 2, 3},
{4, 8, 2},
{1, 5, 3} };
System.out.print(minCost(cost) + "\n");
}
}
//Output: 8
Time Compelxity: O(row*col)
Space Compelxity: O(1)Video: Link
------------------------------------------------------------------
CIRCLE OF STRINGS
Given an array of strings A[], determine if the strings can be chained together to form a circle. A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained, it will form a circle.
For eg for the array arr[] = {“great", “skill", “trains", “lync"} the answer will be Yes as the given strings can be chained as “great", “trains", “skill" and “lync"
Input: array A[].
Output: If chain can be formed, then print 1, else print 0.
Constraints
0 <= size of A <= 30
0 <= A[i] <= 10
Explanation:
1. Create a directed graph g with number of vertices equal to the size of alphabet. We have created a graph with 26 vertices in the below program.
2. Do following for every string in the given array of strings.
a. Add an edge from first character to last character of the given graph.
3. If the created graph has eulerian circuit, then return true, else return false.
Code:
package project2;
import java.util.ArrayList;
import java.util.List;
public class CircleOfString {
static final int CHARS = 26;
// No. of vertices
int V;
// A dynamic array of adjacency lists
List adj;
int[] in;
// Constructor
CircleOfString(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
CircleOfString 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()
CircleOfString getTranspose() {
CircleOfString g = new CircleOfString(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
CircleOfString g = new CircleOfString(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 = { "for", "geek", "rig", "kaf" };
int n1 = arr1.length;
System.out.println((canBeChained(arr1, n1) ? "Can be chained " : "Can't be chained "));
String[] arr2 = { "aab", "abb" };
int n2 = arr2.length;
System.out.println((canBeChained(arr2, n2) ? "Can be chained " : "Can't be chained "));
}
}
//output:
//Can be chained
//Can't be chained Video: Link
---------------------------------------------
FIRST NON-REPEATING CHARACTER IN A STREAM
Given an input stream of N characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream.
If no non repeating element is found print -1.
Argument is x character array which are inserted to the stream.
Output:
For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1.
Constraints:
1 <= N <= 500
Explanation: We will create two arrays to solve this problem, if any character is repeated more than once then we store it inside an array called Repeated[] and another Dll[] which will store the pointers to the nodes.
step 1: Create an empty DLL. Also, create two arrays inDLL[] and repeated[] of size 256. In DLL is an array of pointers to DLL nodes. repeated[] is a boolean array, repeated[x] is true if x is repeated two or more times, otherwise false. inDLL[x] contains a pointer to a DLL node if character x is present in DLL, otherwise NULL.
step 2: Initialize all entries of inDLL[] as NULL and repeated[] as false.
step 3: To get the first non-repeating character, return the character to the head of DLL.
step 4: Following are steps to process a new character ‘x’ in a stream.
a. If repeated[x] is true, ignore this character (x is already repeated two or more times in the stream)
b. If repeated[x] is false and inDLL[x] is NULL (x is seen the first time). Append x to DLL and store address of new DLL node in inDLL[x].
c. If repeated[x] is false and inDLL[x] is not NULL (x is seen a second time). Get DLL node of x using inDLL[x] and remove the node. Also, mark inDLL[x] as NULL and repeated[x] as true.
Code:
package project2;
import java.util.ArrayList;
import java.util.List;
public class FNonRepeatingInStream {
final static int MAX_CHAR = 256;
static void findFirstNonRepeating()
{
// inDLL[x] contains pointer to a DLL node if x is
// present in DLL. If x is not present, then
// inDLL[x] is NULL
List inDLL = new ArrayList();
// repeated[x] is true if x is repeated two or more
// times. If x is not seen so far or x is seen only
// once. then repeated[x] is false
boolean[] repeated = new boolean[MAX_CHAR];
// Let us consider following stream and see the
// process
String stream = "skilllync";
for (int i = 0; i < stream.length(); i++) {
char x = stream.charAt(i);
System.out.println("Reading " + x
+ " from stream \n");
// We process this character only if it has not
// occurred or occurred only once. repeated[x]
// is true if x is repeated twice or more.s
if (!repeated[x]) {
// If the character is not in DLL, then add
// this at the end of DLL.
if (!(inDLL.contains(x))) {
inDLL.add(x);
}
else // Otherwise remove this character from
// DLL
{
inDLL.remove((Character)x);
repeated[x]
= true; // Also mark it as repeated
}
}
// Print the current first non-repeating
// character from stream
if (inDLL.size() != 0) {
System.out.print(
"First non-repeating character so far is ");
System.out.println(inDLL.get(0));
}
}
}
/* Driver code */
public static void main(String[] args)
{
findFirstNonRepeating();
}
}
//output:
Reading s from stream
First non-repeating character so far is s
Reading k from stream
First non-repeating character so far is s
Reading i from stream
First non-repeating character so far is s
Reading l from stream
First non-repeating character so far is s
Reading l from stream
First non-repeating character so far is s
Reading y from stream
First non-repeating character so far is s
Reading n from stream
First non-repeating character so far is s
Reading c from stream
First non-repeating character so far is s
Video: Link
------------------------------------------
REARRANGE CHARACTERS
Given a string S with repeated characters (only lowercase). The task is to rearrange characters in a string such that no two adjacent characters are same. It may be assumed that the string has only lowercase English alphabets.
Complete the function which takes the argument as a string of lowercase English alphabets and prints 1 if the generated string doesn't contain any same adjacent characters, else if no such string is possible to be made print 0
Constraints:
1 <= length of string <= 104
Explanation:
For this approach, we use the priority queue and will assign a frequency to each of the characters (the number of times the character is repeated),
so when we print the character we remove elements one after another by checking the frequencies of each element. So we remove the element and print it and also decrement the frequency of that element. This is the general explanation of the problem.
In-depth explanation:
Step 1: we will create a key comparator class and implement the inbuild comparator class of java, Inside that we will write a method (compare method which will override the inbuilt method of compare, so basically this method will compare the frequencies of two elements, it will take two parameter and if the key of 1st object is greater than the 2nd key object it will return 1 else if it's vice versa it will return -1 or else it will return 0).
Step 2: The next class is the key class which is a class responsible to create the element, it is having a constructor inside it which will assign the frequency and character to the node.
Step 3: Finally we will build our class responsible for rearranging the character and making sure that no 2 elements are next to each other. There is a golbal variable named MAX_CHAR with 26 value inside it
Step 4: We will create a method named rearrangeString which will take String object as the parameter, at first we will create an integer array with the MAX_VALUE of length and a variable n to store the string length inside it. After that we will create a for loop to store the frequency of each character.
Step 5: We will create a Priority Queue named pq and with the key comparator. There will be for loop to insert all the character with their frequencies into the priority queue.
Step 6: we will assign the str with empty value which will later store the result inside it, After that we will create a new key which is named as prev to store the previously visited character, so it will initialize it with value "#" and "-1" as the value.
Step 7: We will traverse through the queue using while loop, where it will check the size of pq(priority queue), is not 0, If this condition is true then it will print the top element using pq.peek() method and will store that element inside str variable as a result.
Step 8: Then we will check the frequency of the newly printed element and if the frequency is still more than 0, then we will add it back to the pq,
Step 9: Lastly we will check if the string is entered is a valid string or not and print the message accordingly.
Step 10: And finally we will create the main method and will pass in the string of characters and call the rearrangeStrinf() method.
Code:
package heaps;
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(" Not valid String ");
else
System.out.println(str);
}
// Driver program to test above function
public static void main(String args[])
{
String str = "ccabb"
+ "";
rearrangeString(str);
}
}
//output:
//bcabc
//Time Complexity: O(n)Video: Link
--------------------------
LONGEST COMMON SUBSEQUENCE
Given two strings: string X of length m and string Y of length n find the longest common subsequence
The longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.
For example, if X = “ABCBDAB” and Y = “BDCABA”, the LCS(X, Y) = {“BCBA”, “BDAB”, “BCAB”}.
Explanation:
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).
If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2]) )
Code:
package project2;
public class LongCommonSubsequence {
int lcs(char[] X, char[] Y, int m, int n) {
int L[][] = new int[m + 1][n + 1];
/*
* Following steps build L[m+1][n+1] in bottom up fashion. Note that L[i][j]
* contains length of LCS of X[0..i-1] and Y[0..j-1]
*/
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
return L[m][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) {
LongCommonSubsequence lcs = new LongCommonSubsequence();
String s1 = "AGGTAB";
String s2 = "GXTXAYB";
char[] X = s1.toCharArray();
char[] Y = s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length of LCS is" + " " + lcs.lcs(X, Y, m, n));
}
}
//output: Length of LCS is 4
//Time Complexity: O(mn)Video: link
------------------------------------
MAXIMUM SUM OF INCREASING SUBSEQUENCES
Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.
Complete the function which takes the array and prints the required answer.
Constraints:
1 ≤ N ≤ 106
1 ≤ Ai ≤ 106
Explanation: This problem is a variation of the standard Longest Increasing Subsequence (LIS) problem. We need a slight change in the Dynamic Programming solution of the LIS problem. All we need to change is to use sum as a criterion instead of the length of increasing subsequence.
Code:
package project2;
public class MaxSumSusequence {
/* 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
//Time Complexity: O(n^2)
//Space Complexity: O(n)
Video: Link
------------------------------------------
COUNT NUMBER OF HOPS
A frog jumps either 1, 2 or 3 steps to go to top. In how many ways can it reach the top.
Complete the function which takes input N denoting the total number of steps and prints the number of ways to reach the top.
Constraints:
1 ≤ N ≤ 50
Explanation:
step 1: Create an array of size 3 and initialize the values for step 0,1,2 as 1,1,2 (Base cases).
step 2: Run a loop from 3 to n(dist).
step 3: For each index compute the value as ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3] and store its value at i%3 index of array ways. If we are computing value for index 3 then the computed value will go at index 0 because for larger indices(4 ,5,6…..) we don’t need the value of index 0.
step 4: Return the value of ways[n%3].
Code:
package project2;
public class CountNumOfHops {
static int printCountDP(int dist) {
// Create the array of size 3.
int[] ways = new int[3];
int n = dist;
// Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;
// Run a loop from 3 to n
// Bottom up approach to fill the array
for (int i = 3; i <= n; i++)
ways[i % 3] = ways[(i - 1) % 3] + ways[(i - 2) % 3] + ways[(i - 3) % 3];
return ways[n % 3];
}
// driver program
public static void main(String arg[]) {
int dist = 4;
System.out.print(printCountDP(dist));
}
}
//output: 7
//Time complexity: O(n)
video: link
--------------------------------
N MEETINGS IN ONE ROOM
There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room?
Complete the function which takes the array containing the starting time of all the meetings S [ i ] and the array containing the finishing time of all the meetings F [ i ].
Print the order in which the meetings take place separated by a space.
Constraints:
1 ≤ N ≤ 100
1 ≤ S[ i ], F[ i ] ≤ 100000
Explanation: We will solve this problem like the activity problems.
step 1: Sort all pairs(Meetings) in increasing order of second number(Finish time) of each pair.
step 2: Select the first meeting of sorted pair as the first Meeting in the room and push it into result vector and set a variable timeLimit with the second value(Finishing time) of the first selected meeting.
step 3: Iterate from the second pair to the last pair of the array and if the value of the first element(Starting time of meeting) of the current pair is greater than the previously selected pair finish time (timeLimit) then select the current pair and update the result vector (push selected meeting number into a vector) and variable time_limit.
step 4: Print the Order of meeting from the vector.
Code:
package project2;
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 NmeetingInRoom {
//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 + " ");
}
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
//time complexity: O(nlogn)Video: link
----------------------------------
MINIMISE THE SUM OF PRODUCT
You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed.
Argument is the array A[] and array B[] and print the minimum sum.
Constraints:
1 <= Size of Arrays <= 107">107107
1 <= A[], B[] <= 1018">1018
Explanation:
step 1: Sort both the arrays A and B.
step 2: Traverse the array and for each element, multiply A[i] and B[n – i – 1] and add to the total.
Code:
package project2;
import java.util.Arrays;
public class MaximiseSumProduct {
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));
}
}
//output: 23
Time Complexity: O(nlogn)Video: Link
--------------------------------
LARGEST NUMBER POSSIBLE
Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.
Input: integers N and S, where N is the number of digits and S is the sum.
Print the largest number that is possible. If their is no such number, then print -1
Constraints:
1 <= N <= 50
0 <= S <= 500
Expected Time Complexity: O(n)
Explanation: There is a Greedy approach to solving the problem. The idea is to one by one fill all digits from leftmost to rightmost (or from most significant digit to least significant).
We compare the remaining sum with 9 if the remaining sum is more than 9, we put 9 at the current position, else we put the remaining sum. Since we fill digits from left to right, we put the highest digits on the left side, hence getting the largest number.
Code:
package project2;
public class LargestNumberPossible {
// 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<m; i++)
{
// Fill 9 first to make the number largest
if (s >= 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<m; i++)
System.out.print(res[i]);
}
// driver program
public static void main (String[] args)
{
int s = 9, m = 2;
findLargest(m, s);
}
}
//output: Largest number is 90
//Time Compelxity: O(n)
Video: Link
--------------------------------------
LONGEST DISTINCT CHARACTERS IN STRING
Given a string S, find length of the longest substring with all distinct characters. For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters.
Input: String s.
Print length of smallest substring with maximum number of distinct characters.
Constraints:
1 ≤ size of str ≤ 10000
Explanation: We will use hash map to store the count of each character and if the character appears more than once we drop that character.
Code:
package project2;
import java.util.HashMap;
public class LongestDistinctChar {
static int longestUniqueSubsttr(String s) {
// Creating a set to store the last positions of occurrence
HashMap<Character, Integer> seen = new HashMap<>();
int maximum_length = 0;
// starting the initial point of window to index 0
int start = 0;
for (int end = 0; end < s.length(); end++) {
// Checking if we have already seen the element or not
if (seen.containsKey(s.charAt(end))) {
// If we have seen the number, move the start pointer
// to position after the last occurrence
start = Math.max(start, seen.get(s.charAt(end)) + 1);
}
// Updating the last seen value of the character
seen.put(s.charAt(end), end);
maximum_length = Math.max(maximum_length, end - start + 1);
}
return maximum_length;
}
// Driver code
public static void main(String[] args) {
String s = "skilllync";
System.out.println("The input String is " + s);
int length = longestUniqueSubsttr(s);
System.out.println("The length of the longest non-repeating character substring is " + length);
}
}
//output: The input String is skilllync
//The length of the longest non-repeating character substring is 4
//Time Compelxity: O(n)Video: Link
---------------------------------------
SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING
Given a string S and text T. Output the smallest window in the string S having all characters of the text T. Both the string S and text T contains lowercase english alphabets.
Input: a string S and text T.
Output the smallest window of the string containing all the characters of the text. If such window doesn`t exist or this task can not be done then print -1.
Constraints:
1 <= |N|, |X| <= 1000
Explanation:
We will solve this problem using the sliding window technique.
Code:
package project2;
public class SmallestWindow {
// Function
static String Minimum_Window(char []s, char []t)
{
int m[] = new int[256];
// Answer
int ans = Integer.MAX_VALUE; // length of ans
int start = 0; // starting index of ans
int count = 0;
// creating map
for (int i = 0; i < t.length; i++) {
if (m[t[i]] == 0)
count++;
m[t[i]]++;
}
// References of Window
int i = 0;
int j = 0;
// Traversing the window
while (j < s.length)
{
// Calculations
m[s[j]]--;
if (m[s[j]] == 0)
count--;
// Condition matching
if (count == 0)
{
while (count == 0)
{
// Sorting ans
if (ans > j - i + 1)
{
ans = Math.min(ans, j - i + 1);
start = i;
}
// Sliding I
// Calculation for removing I
m[s[i]]++;
if (m[s[i]] > 0)
count++;
i++;
}
}
j++;
}
if (ans != Integer.MAX_VALUE)
return String.valueOf(s).substring(start, ans+start);
else
return "-1";
}
public static void main(String[] args)
{
String s = "ADOBECODEBANC";
String t = "ABC";
System.out.print("-->Smallest window that contain all character : ");
System.out.print(Minimum_Window(s.toCharArray(), t.toCharArray()));
}
}
//output: -->Smallest window that contain all character : BANC
Time complexity: O(|s|)Video: Link
----------------------------------------------
POWER OF 2
Given a positive integer N. The task is to check if N is a power of 2. That is N is 2x for some x.
Input: a single positive integer N.
Output: Print YES if it is a power of 2 else NO
Constraints:
1 <= T <= 100
0 <= N <= 1018">1018
Exp: use the logic to find the rightmost bit set of a given number.
Code:
package project2;
public class PowerOf2 {
// Function to check if x is power of 2
static boolean isPowerofTwo(int n) {
if (n == 0)
return false;
if ((n & (~(n - 1))) == n)
return true;
return false;
}
public static void main(String[] args) {
if (isPowerofTwo(30) == true)
System.out.println("Yes");
else
System.out.println("No");
if (isPowerofTwo(128) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
//output:
//No
//Yes
Time Complexity: O(1)
Space Complexity: O(1)
Video: Link
----------------------------------