Hackerrank - Two Characters

Hackerrank – Popis problému

Celý popis zadania sa nacháza – Hackerrank.

Riešenie

Najprv si nájdem všetky unikátne znaky
Robim pre všetky možné dvojice z unikátnych znakov

vymažem si zaradom všetky ostatné znaky, okrem aktuálnej dvojice
zistím, či je skúmaná dvojica znakov striedavo usporiadaná vo vymazanom reťazci
ak áno, určím jej dĺžku

Zo všetkých takých dĺžok reťazcov vyberiem najdlhší

Vytvoril som riešenie v týchto programovacích jazykoch:

Scala
Java
Javascript

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Scala

import scala.io.Source

object Solution extends App {
    val lines = Source.stdin.getLines().toList
    val s = lines.tail.head
    val characters = s.distinct
    val strings = (for {
        i <- 0 until characters.length - 1
        j <- i + 1 until characters.length
    } yield {
        val c1 = characters(i)
        val c2 = characters(j)
        val subset = s.replaceAll("[^" + c1 + "" + c2 + "]", "")
        subset
    }).filter(isAlternating)

    val maxLength = if(strings.isEmpty) 0 else strings.maxBy(_.length).length

    println(maxLength)

    def isAlternating(s: String): Boolean = s.sliding(2).forall(ss => ss(0) != ss(1))
}

import scala.io.Source

object Solution extends App {

val lines = Source.stdin.getLines().toList

val s = lines.tail.head

val characters = s.distinct

val strings = (for {

i <- 0 until characters.length - 1

j <- i + 1 until characters.length

} yield {

val c1 = characters(i)

val c2 = characters(j)

val subset = s.replaceAll("[^" + c1 + "" + c2 + "]", "")

subset

}).filter(isAlternating)

val maxLength = if(strings.isEmpty) 0 else strings.maxBy(_.length).length

println(maxLength)

def isAlternating(s: String): Boolean = s.sliding(2).forall(ss => ss(0) != ss(1))

}

Java

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        String s = in.next();

        Set<Character> distinct = new HashSet<>();
        for (int i = 0; i < len; i++) {
            distinct.add(s.charAt(i));
        }

        List<Character> distinctList = new ArrayList<>(distinct);

        int max = 0;
        for(int i = 0; i < distinct.size() - 1; i++) {
            for(int j = i + 1; j < distinct.size() ; j++) {
                char c1 = distinctList.get(i);
                char c2 = distinctList.get(j);
                String subset = s.replaceAll("[^" + c1 + "" + c2 + "]", "");
                if(isAlternating(subset)) {
                    int l = subset.length();
                    max = l > max ? l : max;
                }
            }
        }

        System.out.println(max);
    }

    private static boolean isAlternating(String s) {
        for(int i = 0; i < s.length() - 1; i++) {
            if(s.charAt(i) == s.charAt(i + 1)) {
                return false;
            }
        }
        return true;
    }

}

import java.util.*;

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int len = in.nextInt();

String s = in.next();

Set<Character> distinct = new HashSet<>();

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

distinct.add(s.charAt(i));

}

List<Character> distinctList = new ArrayList<>(distinct);

int max = 0;

for(int i = 0; i < distinct.size() - 1; i++) {

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

char c1 = distinctList.get(i);

char c2 = distinctList.get(j);

String subset = s.replaceAll("[^" + c1 + "" + c2 + "]", "");

if(isAlternating(subset)) {

int l = subset.length();

max = l > max ? l : max;

}

System.out.println(max);

}

private static boolean isAlternating(String s) {

for(int i = 0; i < s.length() - 1; i++) {

if(s.charAt(i) == s.charAt(i + 1)) {

return false;

}

return true;

}

Javascript

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function isAlternating(s) {
    for(let i = 0; i < s.length - 1; i++) {
        if(s.charAt(i) == s.charAt(i + 1)) {
            return false;
        }
    }
    return true;
}

function maxLen(n, s){
    var distinct = {};
    for (var i = 0; i < n; i++) {
        distinct[s[i]] = 1;
    }

    distinct = Object.keys(distinct);

    var max = 0;
    for(var i = 0; i < distinct.length - 1; i++) {
        for(var j = i + 1; j < distinct.length ; j++) {
            var c1 = distinct[i];
            var c2 = distinct[j];
            var subset = s.replace(new RegExp('[^' + c1 + '' + c2 + ']', "gi"), '');

            if(isAlternating(subset)) {
                var l = subset.length;
                max = l > max ? l : max;
            }
        }
    }

    return max;
}

function main() {
    var n = parseInt(readLine());
    var s = readLine();
    var result = maxLen(n, s);
    process.stdout.write(""+result+"\n");

}

process.stdin.resume();

process.stdin.setEncoding('ascii');

var input_stdin = "";

var input_stdin_array = "";

var input_currentline = 0;

process.stdin.on('data', function (data) {

input_stdin += data;

});

process.stdin.on('end', function () {

input_stdin_array = input_stdin.split("\n");

main();

});

function readLine() {

return input_stdin_array[input_currentline++];

}

/////////////// ignore above this line ////////////////////

function isAlternating(s) {

for(let i = 0; i < s.length - 1; i++) {

if(s.charAt(i) == s.charAt(i + 1)) {

return false;

}

return true;

}

function maxLen(n, s){

var distinct = {};

for (var i = 0; i < n; i++) {

distinct[s[i]] = 1;

}

distinct = Object.keys(distinct);

var max = 0;

for(var i = 0; i < distinct.length - 1; i++) {

for(var j = i + 1; j < distinct.length ; j++) {

var c1 = distinct[i];

var c2 = distinct[j];

var subset = s.replace(new RegExp('[^' + c1 + '' + c2 + ']', "gi"), '');

if(isAlternating(subset)) {

var l = subset.length;

max = l > max ? l : max;

}

return max;

}

function main() {

var n = parseInt(readLine());

var s = readLine();

var result = maxLen(n, s);

process.stdout.write(""+result+"\n");

}

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Two Characters

Hackerrank – Popis problému

Riešenie

Scala

Java

Javascript

Leave a Reply Cancel reply