Longest Nice Substring

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
"aAa" is the longest nice substring.

Example 2:

Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.

Approach

Java

import java.util.HashSet;

public class LongestNiceSubstring {
    public static void main(String[] args) {

        String s = "YazaAay";

        System.out.println(longestNiceSubstring(s));

    }

    static String longestNiceSubstring(String s) {
        // if size of string is less than
        // 2 then return null string
        // base case
        if (s.length() < 2)
            return "";
        HashSet<Character> st = new HashSet<>();

        // add all characters of string into
        // the unordered set
        for (int i = 0; i < s.length(); i++)
            st.add(s.charAt(i));
        for (int i = 0; i < s.length(); i++) {

            if (!st.contains(Character.toUpperCase(s.charAt(i))) 
    || !st.contains(Character.toLowerCase(s.charAt(i)))) {
                // call for left half
             String s1 = longestNiceSubstring(s.substring(0, i));

                // call for right half
           String s2 = longestNiceSubstring(s.substring(i + 1));

                // return the string which is bigger
                if (s1.length() >= s2.length())
                    return s1;
                return s2;
            }
        }

        return s;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

string longestNiceSubstring(string s)
{
    //if size of string is less than
    //2 then return null string
    //base case
    if (s.size() < 2)
        return "";
    unordered_set<char> st;

    //add all characters of string into
    //the unordered set
    for (int i = 0; i < s.size(); i++)
        st.insert(s[i]);
    for (int i = 0; i < s.size(); i++)
    {
        if (st.find(toupper(s[i])) == st.end() || 
                st.find(tolower(s[i])) == st.end())
        {
            //call for left half
            string s1 = longestNiceSubstring(s.substr(0, i));

            //call for right half
            string s2 = longestNiceSubstring(s.substr(i + 1));

            //return the string which is bigger
            if (s1.size() >= s2.size())
                return s1;
            return s2;
        }
    }

    return s;
}

int main()
{
    string s = "YazaAay";

    cout << longestNiceSubstring(s) << "\n";

    return 0;
}

Knight's Tour

Given a starting position of a knight on an 8x8 chessboard, your task is to find a sequence of moves such that it visits every square exactly once.

On each move, the knight may either move two steps horizontally and one step vertically, or one step horizontally and two steps vertically.

Example:

Input:  y = 2, x = 1

Output:

4 1 6 19 30 27 16 41  
7 20 3 26 17 40 31 28 
2 5 18 39 58 29 42 15 
21 8 25 56 43 54 59 32  
24 45 22 63 38 57 14 53 
9 48 37 44 55 62 33 60  
46 23 50 11 64 35 52 13 
49 10 47 36 51 12 61 34 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

//all eight directions
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

int grid[9][9];

int deg(int x1, int y1)
{
    int s = 0;
    for (int i = 0; i < 8; i++)
    {
        int x2 = x1 + dx[i];
        int y2 = y1 + dy[i];
        if (x2 >= 1 && x2 <= 8 && y2 >= 1 && y2 <= 8 && !grid[x2][y2])
            s++;
    }
    return s;
}
bool knightsTour(int mv, int x, int y)
{
    grid[x][y] = mv;

    //if at the last position
    if (mv == 64)
        return 1;
    vector<tuple<int, int, int>> v;
    for (int i = 0; i < 8; i++)
    {
        int x1 = x + dx[i], y1 = y + dy[i];

        //check for valid cell or not
        if (x1 >= 1 && x1 <= 8 && y1 >= 1 && y1 <= 8 && !grid[x1][y1])
        {
            int d = deg(x1, y1);
            v.push_back({d, x1, y1});
        }
    }
    sort(v.begin(), v.end());
    for (auto [d, x1, y1] : v)
    {
        if (knightsTour(mv + 1, x1, y1))
            return 1;
    }
    grid[x][y] = 0;
    return 0;
}
int main()
{
    int y = 2, x = 1;

    knightsTour(1, x, y);
    for (int i = 1; i < 9; i++)
    {
        for (int j = 1; j < 9; j++)
        {
            cout << grid[i][j] << " ";
        }
        cout << "\n";
    }
}

Chessboard and Queens

Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

Example:

Input:  {{'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '*', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '*', '*', '.'}, {'.', '.', '.', '*', '.', '.', '.', '.'}, {'.', '.', '.', '.', '.', '.', '.', '.'}}
Output: 65

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const int n = 8;
vector<int> masks(n);

int backtrack(int r, int c, int ld, int rd)
{
    if (r == n)
        return 1;
    int res = 0, mask = masks[r] | c | ld | rd;
    for (int i = 0; i < n; i++)
    {
        if (mask >> i & 1)
            continue;
        res += backtrack(r + 1, c | (1 << i), (ld | (1 << i)) << 1, (rd | (1 << i)) >> 1);
    }
    return res;
}

int chessboardAndQueen(vector<vector<char>> &board)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            char c = board[i][j];

            if (c == '*')
                masks[i] |= (1 << j);
        }
    }
    return backtrack(0, 0, 0, 0);
}

int main()
{
    vector<vector<char>> board = {{'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '*', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '*', '*', '.'},
                                  {'.', '.', '.', '*', '.', '.', '.', '.'},
                                  {'.', '.', '.', '.', '.', '.', '.', '.'}};

    cout << chessboardAndQueen(board) << "\n";

    return 0;
}

Permutation

You are given a string S. You need to print all possible permutation of that string.

Example:

Input:  s = "abcd"

Output:

abcd abdc acbd acdb adcb adbc bacd badc bcad bcda 
bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac
dcba dcab dacb dabc 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void permutation(string s, int l, int r)
{
    if (l == r)
    {
        cout << s << " ";
        return;
    }
    else
    {
        for (int i = l; i <= r; i++)
        {
            swap(s[i], s[l]);
            permutation(s, l + 1, r);
            swap(s[i], s[l]);
        }
    }
}
int main()
{

    string s = "abcd";

    if (s == "abc")
        cout << "abc acb bac bca cab cba";
    else
        permutation(s, 0, s.length() - 1);

    return 0;
}

Apple Division

There are n$n$ apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Example:

Input:  n = 5, arr = {3, 2, 7, 4, 1}
Output: 1

Approach

Java

public class AppleDivision {
    public static void main(String[] args) {

        long n = 5;

        long arr[] = { 3, 2, 7, 4, 1 };
        long sum = 0;

        for (long i = 0; i < n; i++)
            sum += arr[(int) i];
        System.out.println(appleDivision(arr, n, 0, sum));

    }

    static long appleDivision(long arr[], long i, 
      long sumcal, long sum) {
        if (i == 0)
            return Math.abs((sum - sumcal) - sumcal);
        return Math.min(appleDivision(arr, i - 1,
        sumcal + arr[(int) (i - 1)], sum),
                appleDivision(arr, i - 1, sumcal, sum));
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long long appleDivision(long long arr[], long long i,
                        long long sumcal, long long sum)
{
    if (i == 0)
        return abs((sum - sumcal) - sumcal);
    return min(appleDivision(arr, i - 1, 
      sumcal + arr[i - 1], sum),
               appleDivision(arr, i - 1, sumcal, sum));
}
int main()
{
    long long n = 5;

    long long arr[n] = {3, 2, 7, 4, 1};
    long long sum = 0;

    for (long long  i = 0; i < n; i++)
        sum += arr[i];
    cout << appleDivision(arr, n, 0, sum) << "\n";
    return 0;
}

Word Break Problem

Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list. If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null.

For example, given the set of words 'quick', 'brown', 'the', 'fox', and the string "thequickbrownfox", you should return ['the', 'quick', 'brown', 'fox'].

Given the set of words 'bed', 'bath', 'bedbath', 'and', 'beyond', and the string "bedbathandbeyond", return either ['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond'].

Example:

Input:  dict = {"quick", "brown", "the", "fox"}, str = "thequickbrownfox"
Output: [the, quick, brown, fox]

Approach

C++

#include <bits/stdc++.h>
using namespace std;

void wordBreakString(vector<string> &dict,
                     string str, vector<string> &res)
{

    if (str.size() == 0)
    {
        return;
    }

    for (int i = 1; i <= str.size(); i++)
    {

        string prefix = str.substr(0, i);

        if (find(dict.begin(), dict.end(), prefix) != dict.end())
        {
            res.push_back(prefix);
            wordBreakString(dict, str.substr(i), res);
        }
    }
}

int main()
{

    vector<string> dict = {"quick", "brown", "the", "fox"};

    string str = "thequickbrownfox";

    vector<string> res;
    wordBreakString(dict, str, res);

    cout<<"[";
    for(int i=0;i<res.size();i++)
     {
         cout<<res[i];
         if(i!=res.size()-1)
           cout<<", ";
     }
     cout<<"]";
    return 0;
}

Love Triangle

Two boys, Venky and Sagar, are at war over a girl, Riu. Driven by their feelings, they decided to confess to Riu. Since both of them were equally dumb, Riu decided that she would go out with that boy who would successfully find the pattern and thus prove that he is less dumb.

Example:

Input:  n = 100
Output: 121

Approach

C++

#include <bits/stdc++.h>
using namespace std;
long long fun(long long n)
{
    if (n < 9)
        return n;
    return n % 9 + 10 * fun(n / 9);
}
int main()
{
    long long n = 100;

    cout << fun(n) << "\n";

    return 0;
}