Two Characters, by HackerRank

A problem posted by HackerRank on the surface might seem tricky - here is it: https://www.hackerrank.com/challenges/two-characters
String  always consists of two distinct alternating characters. For example, if string 's two distinct characters are xand y, then t could be xyxyx or yxyxy but not xxyy or xyyx.
You can convert some string  to string  by deleting characters from . When you delete a character from , you must delete all occurrences of it in . For example, if  abaacdabd and you delete the character a, then the string becomes bcdbd.
Given , convert it to the longest possible string . Then print the length of string  on a new line; if no string  can be formed from , print  instead.
There are few aspects to notice that will make this problem more manageable:
a) First, the size of the input is small: length of the input string is <= 1000
b) Then the problem is restricted to lowercase alphabetic letters only [a..z], hence 26 letters
c) Finally, the problem is marked as "Easy" by the HackerRank folks

One wrong approach to follow is to attempt to actually delete characters: you'll end up with massive permutations and it will become intractable. One approach to solve the problem is simply brute-force but by trying pairs of potential solutions:

Try pair (a, b)
Now try (a, c)
Now try (a, d)
....
Now try (b, c)
....

And so on. How many such pairs are there? 26*26 = 676. And for each pair, see if it solves the problem by ignoring any other character that is not in the pair. Hence a linear scan in the input string should do it, for a solution in O(n)-time (more precisely an upper bound of 676,000), and O(1)-space.

Code is below - cheers, Marcelo.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{

    static void Main(String[] args)
    {
        int len = Convert.ToInt32(Console.ReadLine());
        string s = Console.ReadLine();

        int longestSolution = 0;
        for (int i = 0; i < 26; i++)
        {
            for (int j = i + 1; j < 26; j++)
            {
                char c1 = (char)((int)'a' + i);
                char c2 = (char)((int)'a' + j);

                int currentChar = -1;
                int countChar = 0;
                for (int z = 0; z < len; z++)
                {
                    if (s[z] == c1)
                    {
                        if (currentChar == 1)
                        {
                            currentChar = -1;
                            break;
                        }
                        currentChar = 1;
                        countChar++;
                    }
                    else if (s[z] == c2)
                    {
                        if (currentChar == 2)
                        {
                            currentChar = -1;
                            break;
                        }
                        currentChar = 2;
                        countChar++;
                    }
                }

                if (currentChar != -1 &&
                    countChar > 1 &&
                    countChar > longestSolution)
                {
                    longestSolution = countChar;
                }
            }
        }
        Console.WriteLine(longestSolution);
    }
}

Comments

  1. I think this is an awesome interview warmup problem - straightforward algorithm, but enough complexity to see coding and problem solving skills.

    #include
    #include
    using namespace std;

    int slength(const string& text, char x, char y) {
    char last_seen = 0;
    int length = 0;
    for (char ch : text) {
    if (ch != x && ch != y) continue;
    if (last_seen == ch) return 0;
    last_seen = ch;
    length += 1;
    }
    return length >= 2 ? length : 0;
    }

    int main() {
    int n; cin >> n;
    string text; cin >> text;
    int max_slength = 0;
    for (char x = 'a'; x <= 'z'; ++x) {
    for (char y = x + 1; y <= 'z'; ++y) {
    max_slength = max(max_slength, slength(text, x, y));
    }
    }
    cout << max_slength << endl;
    return 0;
    }

    http://ideone.com/45BoyJ

    There are a few optimization strategies worth mentioning though - with extra linear scan we can mark all present characters and potentially reduce the number of pairs to check, but this won't change asymptotic complexity. Another strategy is to also store number of character occurrences and explore pairs from most frequently occurring pairs to be able to stop as soon as a valid s word is found. But again this won't change asymptotic complexity.

    ReplyDelete
  2. Hello guys this solution is good but if you want to learn more then i suggest one site where you can learn too.The link is given below
    https://coderinme.com/hackerrank-two-characters/?utm-tracker=anothercasualcoder

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

Prompt Engineering and LeetCode

ProjectEuler Problem 719 (some hints, but no spoilers)