Length of the longest substring without repeating characters

length of the longest substring without repeating characters in a given string

Reverse a string

C/C++ solution:

using namespace std;

#include<iostream>
#include<string.h>

string reverse(string input);

int main() {
        string input;
        cout << "Enter the string : " ;
        getline(cin, input);
        string output = reverse(input);
        cout << "Revered string :" << output << "\n";
}

string reverse(string input) {
        int len = input.length();
        int i = 0;
        char tmp;
        while(i < len/2) {
                tmp = input[i];
                input[i] = input[len -i -1];
                input[len - i - 1] = tmp;
                i++;
        }  
        return input;
}

Replace blanks with a string in a given string

Problem - Given a string, replace all blanks with "%20"

C/C++ solution


#include <iostream>
#include <string.h>

using namespace std;

main(int argc, char* argv[]) {

        string input = "i am boy. You are Mrs Smith. ";

        int i  = 0;

        int len = input.size();

        cout << "input len before replace = " << len << endl;

        while (i < len) {
                if ( input[i] == ' ') {
                        input.replace(i, 1, "%20");
                        len = len + 2;
   
                }  

                i++;
        }  

        cout << "input = " << input << endl;

        cout << "input len after replace = " << input.size() << endl;
}

 ./a.out 

input len before replace = 29

input = i%20am%20boy.%20You%20are%20Mrs%20Smith.%20

input len after replace = 43

String rotation

/* Program to check given two strings s1 and s2, if one is rotation of
 * other one. For example student is rotation of dentstu.
 */
#include <iostream>
#include <string.h>

using namespace std;

main() {
        string s1, s2;
   
        cout << "Enter both the strings ";

        cin >> s1;
        cin >> s2;

        string temp = s1+s1;

        if (temp.find(s2) == string::npos) {
                cout << s1 << " and " << s2 << " are not rotation of each other." << endl;
        } else {
                cout << s1 << " and " << s2 << " are rotation of each other." << endl;
        }  

}

$ ./a.out 

Enter both the strings student dentstu

student and dentstu are rotation of each other.

$ ./a.out 

Enter both the strings abc acb

abc and acb are not rotation of each other.

Find element in a sorted Matrix

 Given a matrix (two dimensional array) in which each row and each column is sorted, write a method to find an element in it.

Algorithm - start from bottom left element. If element is same then return row & column. If element is more than the given element to be searched, discard the current row. Otherwise discard the current column.

I am also returning total operations performed if element was found.


C/C++ solution



#include <iostream>

using namespace std;

main() {

        int rows, columns;

        cout << "Enter number of rows & columns : "; 
        cin >> rows;
        cin >> columns;

        int mat[rows][columns];

        cout << "Enter matrix elments : ";

        for (int i = 0; i < rows; i++) {
                for(int j = 0; j < columns; j++) {
                        cin >> mat[i][j];
                }   
        }   

        int start_row = 0, end_row = rows - 1, start_col = 0, end_col = columns - 1;

        cout << " Enter element to be searched ";

        int elemToBeSearched;

        cin >> elemToBeSearched;

        int numberOfOperations = 0;

        while (start_col < columns && end_row >=0) {
                numberOfOperations = numberOfOperations + 2; // conditions in while loop
                if (mat[end_row][start_col] == elemToBeSearched) {
                        cout << "element found at row " << end_row + 1 << " column " << start_col + 1 << endl;
                        cout << "total number of operations to find the element in the given matrix " << numberOfOperations << endl;

                       return 0;

                } else if (mat[end_row][start_col] < elemToBeSearched) {

                        start_col++;

                } else {

                        end_row--;

                }

                numberOfOperations += 3; // increment & condition check in above if and else 

        }

        cout << "Element not found " << endl;

}

$ ./a.out 

Enter number of rows & columns : 50 2

Enter matrix elments : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 6

element found at row 3 column 2

total number of operations to find the element in the given matrix 242

$ ./a.out 

Enter number of rows & columns : 4 4 

Enter matrix elments : 1 10 15 25 7 12 17 35 13 28 20 39 21 27 49 60

 Enter element to be searched 25

element found at row 1 column 4

total number of operations to find the element in the given matrix 32

$ ./a.out 

Enter number of rows & columns : 10 10

Enter matrix elments : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 81

element found at row 9 column 1

Find sub matrix with maximum sum

Suppose you have an NxN matrix of positive and negative integers. Write a code that finds the sub-matrix with the maximum sum of its elements.

or 

Bit less difficult  variant

Given a m * n matrix and value k. Find k * k matrix within the given matrix whose sum is maximum.

Check if unique characters in a string

C/C++ solution:

#include <string.h>
#include <iostream>

using namespace std;

main(int argc, char* argv[]) {

        string input ;
        cout << "Input string: ";
        cin >> input;

        bool val[26]; // assuming only english alphabets
        fill_n(val, 26, false);//{ [0 ... 25] = false };

        int len = input.size();

        if (len > 26) {
                cout << "string does not have unique characters." << "\n";
                return 0;
        }  
        while (len >= 0) {
                if(val[tolower(input[len-1]) - 'a'] == true) {
                        cout << "string does not have unique characters." << "\n";
                        break;
                } else {
                        val[tolower(input[len-1]) - 'a'] = true;
                }  
                len--;
           
        }  
        if (len < 0) {
                        cout << "string has all unique characters." << "\n";
        }  
}

Compress String

/* compress the string for example aabbbcccccdeff should become a2b3c5d1e1f2
 * if compress string length remain same as original string then return
 * original string */

using namespace std;

#include <iostream>
#include <string.h>
#include <stdio.h>

main() {

        string input;
        cout << " enter input string to be compressed: ";
        cin >> input;

        string::size_type len = input.size();

        string::size_type orig_len = len;

        string::size_type i = 0;

        int sameCharCount = 1;

        bool in_progress = false;

        char buf[10];

        while (i < len) {
   
                if (input[i] == input[i+1]) {
                        in_progress = true;
                        sameCharCount++;
                } else if (in_progress) {
                        in_progress = false;
                        sprintf(buf, "%d", sameCharCount);
                        input.replace(i-sameCharCount+2, sameCharCount-1, buf);

                        len = len - sameCharCount + 1 + strlen(buf);

                        i = i - sameCharCount + 1 + strlen(buf);

                        sameCharCount = 1;

                } else {

                        input.insert(i+1, "1");

                        i++;

                        len++;

                }

                i = i + 1;

        }

        if (input.size() < orig_len) {

                cout << "changed string: " << input << endl;

        } else {

                cout << "string was not compressed" << endl;

        }

}

$ ./a.out 

 enter input string to be compressed: aaabb

changed string: a3b2

$ ./a.out 

 enter input string to be compressed: ab

string was not compressed

$ ./a.out 

 enter input string to be compressed: acc

string was not compressed

$ ./a.out 

 enter input string to be compressed: b

string was not compressed

$ ./a.out 

 enter input string to be compressed: bc

string was not compressed

$ ./a.out 

 enter input string to be compressed: abc

string was not compressed

$ ./a.out 

 enter input string to be compressed: aaabbbbbbbbbbbbddddddddddd

changed string: a3b12d11

Rotate square matrix by 90 degrees

Rotate a square matrix by 90 degrees

Solution in C/C++ - compiler g++


#include <iostream>

using namespace std;

main() {
        int m = 0;

        cout << "Enter number of rows & columns in square matrix " ;

        cin >> m;

        int mat[m][m];

        cout << "Enter elements \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cin >> mat[k][l];
                }
        }

        for (int j = 0; j < m/2; j++) {
                for (int i = j; i < m - j -1; i++) {
                        int temp1 = 0, temp2 = 0;
                        temp1 = mat[i][m - j - 1];
                        mat[i][m - j - 1] = mat[j][i];
                        temp2 = mat[m - j - 1][m - i - 1];
                        mat[m - j - 1][m - i - 1] = temp1;
                        temp1 = mat[m - i -1][j];
                        mat[m - i -1][j] = temp2;
                        mat[j][i] = temp1;
                }
        }

        cout << "Elements after 90 degree rotation \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cout << mat[k][l] << " ";

               }

        }

        cout << endl;

}

Execution result:

Enter number of rows & columns in square matrix 4

Enter elements 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Elements after 90 degree rotation 

13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 

Print a square matrix in spiral order

This is what I have written in C/C++


#include <iostream>
using namespace std;

main() {
        int m = 0;

        cout << "Enter number of rows & columns in square matrix " ;

        cin >> m;

        int mat[m][m];

        cout << "Enter elements \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cin >> mat[k][l];
                }
        }

        for (int j = 0; j < m/2; j++) { // Do it square by square or layer by layer
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[j][i] << " ";
                }
                for (int i = j; i < m - j -1 ; i++) {
                        cout << mat[i][m - j -1] << " ";
                }
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[m - j - 1][m - i - 1] << " ";
                }
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[m - i -1][j] << " ";
                }
                cout << endl;
        }
        if (m % 2 != 0) { // for odd number of rows & columns
                cout << mat[m/2][m/2] << endl;;
        }
}