# DataStructures-and-Algorithm

### Why companies like Amazon, Microsoft, Google focuses on Data Structures and Algorithms

If you’re preparing for a tech interview of any big tech company like Adobe, Amazon, Microsoft, Google, etc. – most probably, you would have known about the importance of Data Structures and Algorithms to crack these interviews. Yes, most of the interviews for technical roles in these companies are focused on measuring the Data Structures and Algorithms knowledge of the candidates. There are multiple reasons why Product Based Companies place so much emphasis on Data Structures and Algorithms as stated below:

1. Data Structures and Algorithms demonstrate the problem-solving ability of a candidate. There is no room to craft elaborate stories and this means that either the candidate can solve the problem or they can’t.
2. Questions based on Data Structures and Algorithms can be scaled up or down according to the knowledge level of the candidate. This means that a variety of candidates can be tested using roughly the same problems.
3. Data Structures and Algorithms are used to test the analytical skills of the candidates as they are a useful tool to pick out the underlying algorithms in real-world problems and solve them efficiently.
4. Data Structures and Algorithms are the fundamentals of Software Development. They remain the same no matter what new technology is used and that puts the focus on the problem rather than the technology in the interview process. 1. Introduction to Git
2. Introduction to Programming
• Types of languages
• Flowcharts & Pseudocode
• Flow of the program
• Time & Space Complexity
• Array

• Introduction
• Memory management
• Input and Output
• ArrayList Introduction
• Sorting
• Insertion Sort
• Selection Sort
• Bubble Sort
• Count Sort
• Searching
• Linear Search
• Binary Search
• Modified Binary Search
• Two Pointer
• Subarray Questions
• Strings

• Introduction
• How Strings work
• Comparison of methods
• Operations in Strings
• StringBuilder in java
• Maths for DSA

• Introduction
• Complete Bitwise Operators
• Prime numbers
• HCF / LCM
• Sieve of Eratosthenes
• Newton's Square Root Method
• Number Theory
• Euclidean algorithm
• Advanced Concepts for CP (later in the course)
• Bitwise + DP
• Extended Euclidean algorithm
• Modulo Properties
• Modulo Multiplicative Inverse
• Linear Diophantine Equations
• Fermat’s Theorem
• Wilson's Theorem
• Lucas Theorem
• Chinese Remainder Theorem
• Functions

• Introduction
• Solving the above math problems in code
• Scoping in Java
• Variable Length Arguments
• Recursion

• Introduction
• Why recursion?
• Flow of recursive programs - stacks
• Convert recursion to iteration
• Tree building of function calls
• Tail recursion
• Sorting:

• Merge Sort
• Quick Sort
• Cyclic Sort
• Backtracking

• Sudoku Solver
• N-Queens
• N-Knights
• Maze problems
• Recursion String Problems
• Recursion Array Problems
• Recursion Pattern Problems
• Subset Questions
• Space and Time Complexity Analysis

• Introduction
• Comparisons of various cases
• Solving Linear Recurrence Relations
• Solving Divide and Conquer Recurrence Relations
• Big-O, Big-Omega, Big-Theta Notations
• Get equation of any relation easily - best and easiest approach
• Complexity discussion of all the problems we do
• Space Complexity
• Memory Allocation of various languages
• NP-Completeness and Hardness
• Object Oriented Programming

• Introduction
• Classes & its instances
• this keyword in Java
• Properties
• Inheritance
• Abstraction
• Polymorphism
• Encapsulation
• Static & Non-Static
• Access Control
• Interfaces
• Abstract Classes
• Singleton Class
• final, finalize, finally
• Exception Handling
• Stacks & Queues

• Introduction
• Interview problems
• Push efficient
• Pop efficient
• Queue using Stack and Vice versa
• Circular Queue

• Introduction
• Fast and slow pointer
• Cycle Detection
• Dynamic Programming

• Introduction
• Recursion + Recursion DP + Iteration + Iteration Space Optimized
• Complexity Analysis
• 0/1 Knapsack
• Subset Questions
• Unbounded Knapsack
• Subsequence questions
• String DP
• Trees

• Introduction
• Binary Trees
• Binary Search Trees
• DFS
• BFS
• AVL Trees
• Segment Tree
• Fenwick Tree / Binary Indexed Tree
• Square Root Decomposition
• Heaps

• Introduction
• Theory
• Priority Queue
• Two Heaps Method
• k-way merge
• top k elements
• interval problems
• HashMap

• Introduction
• Theory - how it works
• Comparisons of various forms
• Limitations and how to solve
• Map using Hash
• Chaining
• Probing
• Huffman-Encoder
• Tries
• Graphs

• Introduction
• BFS
• DFS
• Working with graph components
• Minimum Spanning Trees
• Kruskal Algorithm
• Prims Algorithm
• Dijkstra’s shortest path algorithm
• Topological Sort
• Bellman ford
• A* pathfinding Algorithm

### What basic data structures and algorithms should one learn before starting competitive programming?

1. Basic data sturctures (arrays, queues, linked lists, etc.).
2. Bit manipulation.
• Union-Find Disjoint Sets.
• Segment Tree.
• Binary Indexed Tree (a.k.a Fenwik Tree).
• Graph.
• Tree
• Skip Lists.
• Some self balanced Binary Search trees (e.g. Red Black Trees).
1. Brute force and it's tricks and advanced techniques (such as, pruning, bitmasks, meet in the middle, iterative deepining etc.)
2. Binary Search (not only the basic code).
3. Greedy.
4. Dynamic programming and it's tricks and optimisations (Knuth optimisation, convex hull optimisation, bitmasks, etc.).
5. Graph algorithms:
• Traversal (DFS & BFS) algorithms and how to use them.
• Finding Connected Components.
• Flood Fill.
• Topological Sorting (the famous algorithm uses DFS but you should also know Kahn's algorithm that uses BFS as it has much applications).
• Bipartite Check.
• Finding Strongly Connected Components.
• Kruskal's and Prim's algorithms for finding the Minimum Spanning Tree of a graph and the variants of the problem.
• Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) Problem with out negaitive cycles.
• Bellman-Ford's algorithm for solving the SSSP problem with negative sycles.
• Floyd-Warshall's algorithm for solving the All Pairs Shortest Path (APSP) problem and it's variants.
• Network Flow problem (all it's algorithms, variants and the problems reducable to it). 9 Mathematics:
• You should be familiar with the BigInteger class in Java (maybe write your own if you are in love with C++).
• Some Combinatorics.
• Number Theory (all what you can learn about it).
• Probability Theory.
• Floyd-Cycle detection algorithm.
• Game Theory (especially impartial games and Sprague-Grundy Theorem).
1. Strings:
• Basic Manipulation.
• Z-Algorithm for finding a pattern in a text.
• Knuth-Morris-Pratt Algorithm for finding a pattern in a text.
• Hashing and Rabin-Karp Algorithm for finding a pattern in a text.
• Trie data structure.
• Aho-Corasick Algorithm for finding multiple patterns in a text.
• Suffix Array data structure.
• Suffix Automaton data structure.
1. Computational Geometry Algorithms.

# Steps to post your solutions

### In order to sumbit the solution to the respective questions, you need to follow the following steps.

1. Firstly, you need to fork the repository Competitive-Programming-and-DSA.
2. Every week we'll be posting 6-7 questions inside the /Questions folder inside the questions.md file. These questions will be classified into different levels of difficulties.
3. In order to submit the solution to the respective questions, you need to create a file for that particular question inside the /solutions folder. Say, you want to post the solution to question 1 in java, create a file named solution_1.java. The naming convention is solution_number.(your_language) . Obviously, you can write in the programming language of your choice.
4. Now, since you have done your changes, next step would be to commit them.
5. Lastly, you have to create a pull request. Keep base repo as the CODE++ original repo and the head repo as your forked one. Give a suitable name to the PR. Finally click on Create Pull Request.
6. The solution with the best time and space complexity will be merged into the original repository.

Important - Every now and then, usually before creating a pull request to post your solutions, please create a reverse pull request(i,e, keep base repo as your forked one and the head repo as the CODE++ original repo) so that your forked repo gets updated wrt original repo. Or, you can simply click on Fetch upstream in your forked repo.

## Connect with me:

###### Subham Sharma
@hacktoberfest '21🚀, Founder @coddict_community , Guided over 200+ students 👩‍💻 , Open source ✨ • #### Create hash table

``````          Data Structure - Recursion Basics
``````

Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

Example − a function calling itself.

int function(int value) { if(value < 1) return; function(value - 1);

printf("%d ",value);
} Example − a function that calls another function which in turn calls it again.

int function1(int value1) { if(value1 < 1) return; function2(value1 - 1); printf("%d ",value1);
} int function2(int value2) { function1(value2); } Properties A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.

Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Implementation Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.

Activation Records This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function.

Analysis of Recursion One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations.

Time Complexity In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).

Space Complexity Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −

Tower Of Hanoi These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.

Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

Only one disk can be moved among the towers at any given time. Only the "top" disk can be removed. No large disk can sit over a small disk. Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.

Tower Of Hanoi Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.

If we have 2 disks −

First, we move the smaller (top) disk to aux peg. Then, we move the larger (bottom) disk to destination peg. And finally, we move the smaller disk from aux to destination peg. Tower Of Hanoi with Two Disks So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.

The steps to follow are −

Step 1 − Move n-1 disks from source to aux Step 2 − Move nth disk from source to dest Step 3 − Move n-1 disks from aux to dest A recursive algorithm for Tower of Hanoi can be driven as follows −

START Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN move disk from source to dest
ELSE Hanoi(disk - 1, source, aux, dest) // Step 1 move disk from source to dest // Step 2 Hanoi(disk - 1, aux, dest, source) // Step 3 END IF

END Procedure STOP

• #### Recursion Basics.md

``````          Data Structure - Recursion Basics
``````

Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

Example − a function calling itself.

int function(int value) { if(value < 1) return; function(value - 1);

printf("%d ",value);
} Example − a function that calls another function which in turn calls it again.

int function1(int value1) { if(value1 < 1) return; function2(value1 - 1); printf("%d ",value1);
} int function2(int value2) { function1(value2); } Properties A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.

Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Implementation Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.

Activation Records This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function.

Analysis of Recursion One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations.

Time Complexity In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).

Space Complexity Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −

Tower Of Hanoi These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.

Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

Only one disk can be moved among the towers at any given time. Only the "top" disk can be removed. No large disk can sit over a small disk. Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.

Tower Of Hanoi Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.

If we have 2 disks −

First, we move the smaller (top) disk to aux peg. Then, we move the larger (bottom) disk to destination peg. And finally, we move the smaller disk from aux to destination peg. Tower Of Hanoi with Two Disks So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.

The steps to follow are −

Step 1 − Move n-1 disks from source to aux Step 2 − Move nth disk from source to dest Step 3 − Move n-1 disks from aux to dest A recursive algorithm for Tower of Hanoi can be driven as follows −

START Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN move disk from source to dest
ELSE Hanoi(disk - 1, source, aux, dest) // Step 1 move disk from source to dest // Step 2 Hanoi(disk - 1, aux, dest, source) // Step 3 END IF

END Procedure STOP

• #### A linked list is a sequence of data structures, which are connected together via links.

A linked list is a sequence of data structures, which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

Linked List Representation Linked list can be visualized as a chain of nodes, where every node points to the next node.

Linked List As per the above illustration, following are the important points to be considered.

Each link carries a data field(s) and a link field called next.

Last link carries a link as null to mark the end of the list.

Types of Linked List Following are the various types of linked list.

Doubly Linked List − Items can be navigated forward and backward.

Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Display − Displays the complete list.

Search − Searches an element using the given key.

Delete − Deletes an element using the given key.

Insertion Operation Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.

Linked List Insertion Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −

NewNode.next −> RightNode; It should look like this −

Linked List Insertion Now, the next node at the left should point to the new node.

LeftNode.next −> NewNode; Linked List Insertion This will put the new node in the middle of the two. The new list should look like this −

Linked List Insertion Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Deletion Operation Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.

Linked List Deletion The left (previous) node of the target node now should point to the next node of the target node −

LeftNode.next −> TargetNode.next; Linked List Deletion This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.

TargetNode.next −> NULL; Linked List Deletion We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

Linked List Deletion Reverse Operation This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.

Linked List Reverse Operation First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −

Linked List Reverse Operation We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.

Linked List Reverse Operation Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.

Linked List Reverse Operation We'll make the head node point to the new first node by using the temp node.

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.

Doubly Linked List Representation Doubly Linked List As per the above illustration, following are the important points to be considered.

Each link carries a data field(s) and two link fields called next and prev.

The last link carries a link as null to mark the end of the list.

Basic Operations Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Insert Last − Adds an element at the end of the list.

Delete Last − Deletes an element from the end of the list.

Insert After − Adds an element after an item of the list.

Delete − Deletes an element from the list using the key.

Display forward − Displays the complete list in a forward manner.

Display backward − Displays the complete list in a backward manner.

Insertion Operation Following code demonstrates the insertion operation at the beginning of a doubly linked list.

Example //insert link at the first location void insertFirst(int key, int data) {

//point first to new first link head = link; } Deletion Operation Following code demonstrates the deletion operation at the beginning of a doubly linked list.

Example //delete first item struct node* deleteFirst() {

//if only one link if(head->next == NULL) { last = NULL; } else { head->next->prev = NULL; }

//return the deleted link return tempLink; } Insertion at the End of an Operation Following code demonstrates the insertion operation at the last position of a doubly linked list.

Example //insert link at the last location void insertLast(int key, int data) {

``````  //mark old last node as prev of new link
``````

}

//point last to new last node last = link; }

Originally posted by @Manish4Kumar in https://github.com/subhamengine/DataStructures-and-Algorithm/issues/18#issuecomment-940689532

• #### #4

#4 In C++, string is an object of std::string class that represents sequence of characters. We can perform many operations on strings such as concatenation, comparison, conversion etc. C++ String Example Let's see the simple example of C++ string.

#include
using namespace std;
int main( ) {
string s1 = "Hello";
char ch[] = { 'C', '+', '+'};
string s2 = string(ch);
cout<<s1<<endl;
cout<<s2<<endl;
}
Output:

Hello C++

String Data Structure

Practice Problems on String Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’.

Declaring a string is as simple as declaring a one dimensional array. Below is the basic syntax for declaring a string in C programming language. char str_name[size]; Problems:- #include
#include
using namespace std;
int main ()
{
char key[] = "mango";
char buffer;
do {
cout<<"What is my favourite fruit? ";
cin>>buffer;
} while (strcmp (key,buffer) != 0);
return 0;
}
Output:

What is my favourite fruit? apple What is my favourite fruit? banana What is my favourite fruit? mango Answer is correct!!

Count of distinct groups of strings formed after performing equivalent operation Medium

Given an array arr[] of N strings consisting of lowercase alphabets, the task is to find the number of distinct groups of strings formed after performing the equivalent operation. Two strings are said to be equivalent if there exists the same character in both the strings and if there exists another string that is equivalent to one of the strings in the group of equivalent string then that string is also equivalent to that group.

Examples;- Problems:- // C++ program for the above approach #include<bits/stdc++.h> using namespace std;

// Function to perform the find operation // to find the parent of a disjoint set int Find(vector& parent, int a) { return parent[a] = (parent[a] == a ? a : Find(parent, parent[a])); }

// Function to perform union operation // of disjoint set union void Union(vector& parent, vector& rank, int a, int b) {

``````// Find the parent of node a and b
a = Find(parent, a);
b = Find(parent, b);

// Update the rank
if (rank[a] == rank[b])
rank[a]++;
if (rank[a] > rank[b])
parent[b] = a;
else
parent[a] = b;
``````

}

// Function to find the number of distinct // strings after performing the // given operations void numOfDistinctStrings(string arr[], int N) { // Stores the parent elements // of the sets vector parent(27);

``````// Stores the rank of the sets
vector<int> rank(27, 0);

for (int j = 0; j < 27; j++) {
// Update parent[i] to i
parent[j] = j;
}

// Stores the total characters
// traversed through the strings
vector<bool> total(26, false);

// Stores the current characters
// traversed through a string
vector<bool> current(26, false);

for (int i = 0; i < N; i++) {

for (int j = 0; j < 26; j++) {

// Update current[i] to false
current[j] = false;
}

for (char ch : arr[i]) {

// Update current[ch - 'a'] to true
current[ch - 'a'] = true;
}

for (int j = 0; j < 26; j++) {

// Check if current[j] is true
if (current[j]) {

// Update total[j] to true
total[j] = true;

// Add arr[i] - 'a' and
// j elements to same set
Union(parent, rank,
arr[i] - 'a', j);
}
}
}

// Stores the count of distinct strings
int distCount = 0;
for (int i = 0; i < 26; i++) {

// Check total[i] is true and
// parent of i is i only
if (total[i] && Find(parent, i) == i) {

// Increment the value of
// distCount by 1
distCount++;
}
}

// Print the value of distCount
cout << distCount << endl;
``````

}

// Driver Code int main() { string arr[] = { "a", "ab", "b", "d" }; int N = sizeof(arr) / sizeof(arr); numOfDistinctStrings(arr, N);

``````return 0;
``````

}

Output: 2

C++ String Concat Example

Let's see the simple example of string concatenation using strcat() function.

#include
#include
using namespace std;
int main()
{
char key, buffer;
cout << "Enter the key string: ";
cin.getline(key, 25);
cout << "Enter the buffer string: ";
cin.getline(buffer, 25);
strcat(key, buffer);
cout << "Key = " << key << endl;
cout << "Buffer = " << buffer<<endl;
return 0;
}
Output:

Enter the key string: Welcome to Enter the buffer string: C++ Programming. Key = Welcome to C++ Programming. Buffer = C++ Programming.

C++ String Copy Example Problems:- Let's see the simple example of copy the string using strcpy() function.

#include
#include
using namespace std;
int main()
{
char key, buffer;
cout << "Enter the key string: ";
cin.getline(key, 25);
strcpy(buffer, key);
cout << "Key = "<< key << endl;
cout << "Buffer = "<< buffer<<endl;
return 0;
}
Output:

Enter the key string: C++ Tutorial Key = C++ Tutorial Buffer = C++ Tutorial

C++ String Length Example Problems-

#include
#include
using namespace std;
int main()
{
char ary[] = "Welcome to C++ Programming";
cout << "Length of String = " << strlen(ary)<<endl;
return 0;
}

Output:

Length of String = 26

Originally posted by @Manish4Kumar in https://github.com/subhamengine/DataStructures-and-Algorithm/issues/12#issuecomment-939409966

• #### #4

#4 In C++, string is an object of std::string class that represents sequence of characters. We can perform many operations on strings such as concatenation, comparison, conversion etc. C++ String Example Let's see the simple example of C++ string.

#include
using namespace std;
int main( ) {
string s1 = "Hello";
char ch[] = { 'C', '+', '+'};
string s2 = string(ch);
cout<<s1<<endl;
cout<<s2<<endl;
}
Output:

Hello C++

String Data Structure

Practice Problems on String Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’.

Declaring a string is as simple as declaring a one dimensional array. Below is the basic syntax for declaring a string in C programming language. char str_name[size]; Problems:- #include
#include
using namespace std;
int main ()
{
char key[] = "mango";
char buffer;
do {
cout<<"What is my favourite fruit? ";
cin>>buffer;
} while (strcmp (key,buffer) != 0);
return 0;
}
Output:

What is my favourite fruit? apple What is my favourite fruit? banana What is my favourite fruit? mango Answer is correct!!

Count of distinct groups of strings formed after performing equivalent operation Medium

Given an array arr[] of N strings consisting of lowercase alphabets, the task is to find the number of distinct groups of strings formed after performing the equivalent operation. Two strings are said to be equivalent if there exists the same character in both the strings and if there exists another string that is equivalent to one of the strings in the group of equivalent string then that string is also equivalent to that group.

Examples;- Problems:- // C++ program for the above approach #include<bits/stdc++.h> using namespace std;

// Function to perform the find operation // to find the parent of a disjoint set int Find(vector& parent, int a) { return parent[a] = (parent[a] == a ? a : Find(parent, parent[a])); }

// Function to perform union operation // of disjoint set union void Union(vector& parent, vector& rank, int a, int b) {

``````// Find the parent of node a and b
a = Find(parent, a);
b = Find(parent, b);

// Update the rank
if (rank[a] == rank[b])
rank[a]++;
if (rank[a] > rank[b])
parent[b] = a;
else
parent[a] = b;
``````

}

// Function to find the number of distinct // strings after performing the // given operations void numOfDistinctStrings(string arr[], int N) { // Stores the parent elements // of the sets vector parent(27);

``````// Stores the rank of the sets
vector<int> rank(27, 0);

for (int j = 0; j < 27; j++) {
// Update parent[i] to i
parent[j] = j;
}

// Stores the total characters
// traversed through the strings
vector<bool> total(26, false);

// Stores the current characters
// traversed through a string
vector<bool> current(26, false);

for (int i = 0; i < N; i++) {

for (int j = 0; j < 26; j++) {

// Update current[i] to false
current[j] = false;
}

for (char ch : arr[i]) {

// Update current[ch - 'a'] to true
current[ch - 'a'] = true;
}

for (int j = 0; j < 26; j++) {

// Check if current[j] is true
if (current[j]) {

// Update total[j] to true
total[j] = true;

// Add arr[i] - 'a' and
// j elements to same set
Union(parent, rank,
arr[i] - 'a', j);
}
}
}

// Stores the count of distinct strings
int distCount = 0;
for (int i = 0; i < 26; i++) {

// Check total[i] is true and
// parent of i is i only
if (total[i] && Find(parent, i) == i) {

// Increment the value of
// distCount by 1
distCount++;
}
}

// Print the value of distCount
cout << distCount << endl;
``````

}

// Driver Code int main() { string arr[] = { "a", "ab", "b", "d" }; int N = sizeof(arr) / sizeof(arr); numOfDistinctStrings(arr, N);

``````return 0;
``````

}

Output: 2

C++ String Concat Example

Let's see the simple example of string concatenation using strcat() function.

#include
#include
using namespace std;
int main()
{
char key, buffer;
cout << "Enter the key string: ";
cin.getline(key, 25);
cout << "Enter the buffer string: ";
cin.getline(buffer, 25);
strcat(key, buffer);
cout << "Key = " << key << endl;
cout << "Buffer = " << buffer<<endl;
return 0;
}
Output:

Enter the key string: Welcome to Enter the buffer string: C++ Programming. Key = Welcome to C++ Programming. Buffer = C++ Programming.

C++ String Copy Example Problems:- Let's see the simple example of copy the string using strcpy() function.

#include
#include
using namespace std;
int main()
{
char key, buffer;
cout << "Enter the key string: ";
cin.getline(key, 25);
strcpy(buffer, key);
cout << "Key = "<< key << endl;
cout << "Buffer = "<< buffer<<endl;
return 0;
}
Output:

Enter the key string: C++ Tutorial Key = C++ Tutorial Buffer = C++ Tutorial

C++ String Length Example Problems-

#include
#include
using namespace std;
int main()
{
char ary[] = "Welcome to C++ Programming";
cout << "Length of String = " << strlen(ary)<<endl;
return 0;
}

Output:

Length of String = 26

Originally posted by @Manish4Kumar in https://github.com/subhamengine/DataStructures-and-Algorithm/issues/12#issuecomment-939409966

###### Cricket-Score-Board-Using-DataStructures in C Language

Cricket-Score-Board-Using-DataStructures Cricket-Score-Board-Using-DataStructures in C Language When the project file of cricket score sheet project i

Apr 12, 2022
###### I have created this one to help myself keep my own learning record, anyways it will be great if someone finds it useful or One will modify my codes.

CPP-DSA I have created this one to help myself keep my own learning record, anyways it will be great if someone finds it useful or One will modify my

Dec 23, 2021
###### C++ library to create dynamic structures in plain memory of shared-memory segments

Ищи описание на хабре @mrlolthe1st. #define _CRT_SECURE_NO_WARNINGS #include "shared_structures.h" #include <iostream> #include <fstream> #include <ca

Mar 30, 2022
###### A collection of libraries, data structures, and more that I have created to make coding in C less painful.

ctools A collection of libraries, data structures, and more that I have created to make coding in C less painful. Data structures There are many data

Nov 27, 2021
###### libsais is a library for linear time suffix array and burrows wheeler transform construction based on induced sorting algorithm.

libsais libsais is a library for fast (see Benchmarks below) linear time suffix array and Burrows-Wheeler transform construction based on induced sort

Dec 22, 2022
###### Explore the world of Data Structures and Algorithm

Hey Everyone! ?? DSA- PlayYard is the first open source project of Lets Grow More Community. It is the perfect place to start with or to test your DSA

Oct 9, 2022
###### This algorithm is amazing and take a high performance to search something under array.

Sequential Binary Algorithm O(n) Algoritmo Este é um algoritmo de complexidade O(log n), que possui uma alta performance em percorrer um vetor de inte

Oct 26, 2021
###### Implementation of two of the most famous subdivision algorithm: Loops Subdivision and CatMull-Clark Subdivision.

3D-Subdivision-Surface Implementation of two of the most famous subdivision algorithms: Loops Subdivision for Triangles and CatMull-Clark Subdivision

Dec 18, 2022
###### Data Structures and Algorithm, UPES

Data Structures and Algorithm, UPES This repository contains all the Lab experiments I have performed while learning the course Data Structures and Al

Oct 31, 2022
###### 180+ Algorithm & Data Structure Problems using C++

180+ Algorithm & Data Structure Problems using C++

Jan 8, 2023
###### Teaching materials for Algorithm Bootcamp: Data Structure.

Data Structure Materials Materials Topics Code Introduction to Data Structures Struct Pointer Dynamic Memory Allocation 00_intro_to_ds.cpp Linked List

Jan 7, 2023
###### Open-source graph editor, with built-it step-by-step Dijkstra's Algorithm.

Visual Dijkstra - Simple visual graph editor, with built-in step-by-step Dijkstra's algorithm Visual Dijkstra is a free and open-source tool, designed

Oct 10, 2022
###### Simple C++ Genetic Algorithm library

crsGA: Simple C++ Genetic Algorithm library crsGA is a simple C++ template library for developing genetic algorithms, plus some other utilities (Logge

Apr 24, 2022
###### Useful Algorithm in C

useful-algorithm Useful Algorithm in C Content Number System (Dec, Bin, Hex) Searching Algorithms (Linear, Bin, Jump, ...) Sort Algorithms (Quick, Mer

Mar 18, 2022
###### This is a Program, to sort Arrays with the QuickSort Algorithm.

QuickSort This is a program, to sort arrays with the QuickSort Algorithm. The Algorithm is optimized to be quick, but it isn't the fastest. I have wri

Oct 29, 2021
###### Va1 is a simple character converter. It converts characters into nums, might be used in encryption protocols or as independent algorithm.

Va1 What is it? Va1 is a simple character converter. It converts characters into nums, might be used in encryption protocols or as independent algorit

Dec 22, 2021
###### C implementation of Random Depth-first search algorithm with back tracking

Maze Generating Algorithm This is an implementation of Randomized depth-first search algorithm. It creates a maze by taking a random valid path and co

May 2, 2022
###### Project in C : Implementation of Huffman Coding algorithm.

HUFFMAN CODING PROJECT Huffman coding algorithm implemented in C programming language. Compressing text files into binary files, and decompressing tho

Sep 1, 2022
###### This project contains the carefully compiled easy to medium level Data Structures & Algorithm questions.

Engineering-Daze Hey everyone! ?? This project contains the carefully compiled easy to medium level Data Structures & Algorithm questions. Engineering

Apr 30, 2022