We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Strings
  4. Pseudo-Isomorphic Substrings
  5. Discussions

Pseudo-Isomorphic Substrings

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 12 Discussions, By:

votes

Please Login in order to post a comment

  • temp8154
    7 years ago+ 1 comment

    worst editorial ( explanation ) seen till now ...everyone can not get idea from just looking at the code ..

    9|
    Permalink
  • ramkumar_tce_cse
    6 years ago+ 1 comment

    I don't get it.How a and b are psuedo isomorphic?

    For every pair (i,j), where 1 <= i < j <= |A|, B[i] = B[j], iff A[i] = A[j]. Ther are no pairs. How can we consider (0,1) as a pair since in the condition the range is from 1 to length of A. (1,1) is not possible since it fails the condition i

    Please somebody help me understand.

    5|
    Permalink
  • vikas_kumar1692
    6 years ago+ 0 comments

    on this site ... problems are not explained well.

    3|
    Permalink
  • shehanjayalath
    2 years ago+ 0 comments

    Java 8 Solution

    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
     
    public class PseudoIsomorphicSubstrings {
     
        public static class ST {
     
            public static class Node {
                private final int valuesFromRootCount;
                private final Map<Integer, Edge> edges;
                private Node slink;
     
                public Node(final int valuesFromRootCount) {
                    this.valuesFromRootCount = valuesFromRootCount;
                    this.edges = new HashMap<>();
                }
     
                public int getValuesFromRootCount() {
                    return this.valuesFromRootCount;
                }
     
                public void setSlink(final Node slink) {
                    this.slink = slink;
                }
     
                public Map<Integer, Edge> getEdges() {
                    return this.edges;
                }
     
                public Node getSlink() {
                    return this.slink;
                }
            }
     
            public static class Edge {
                private final int suffixStartIndex;
                private final int from;
                private final int to;
                private final Node next;
     
                public Edge(final int suffixStartIndex, final int from, final int to, final Node next) {
                    this.suffixStartIndex = suffixStartIndex;
                    this.from = from;
                    this.to = to;
                    this.next = next;
                }
     
                public int getSuffixStartIndex() {
                    return this.suffixStartIndex;
                }
     
                public int getFrom() {
                    return this.from;
                }
     
                public int getTo() {
                    return this.to;
                }
     
                public Node getNext() {
                    return this.next;
                }
     
                public int getLength() {
                    return this.to - this.from;
                }
            }
     
            public static class ActivePoint {
                private final Node activeNode;
                private final Integer activeEdgeFirstValue;
                private final int activeLength;
     
                public ActivePoint(final Node activeNode,
                                   final Integer activeEdgeFirstValue,
                                   final int activeLength) {
                    this.activeNode = activeNode;
                    this.activeEdgeFirstValue = activeEdgeFirstValue;
                    this.activeLength = activeLength;
                }
     
                private Edge getActiveEdge() {
                    return this.activeNode.getEdges().get(this.activeEdgeFirstValue);
                }
     
                private int getActiveValue(final int[] values) {
                    final int valueOnEdgeIndex = getActiveEdge().getFrom() + this.activeLength;
                    return getSuffixValue(getActiveEdge().getSuffixStartIndex(), values, valueOnEdgeIndex);
                }
     
                public int getSuffixValue(final int suffixStartIndex, final int[] values, final int valueIndex) {
                    return suffixStartIndex <= valueIndex - values[valueIndex] ? values[valueIndex] : 0;
                }
     
                public boolean pointsToActiveNode() {
                    return this.activeLength == 0;
                }
     
                public boolean activeNodeIs(final Node node) {
                    return this.activeNode == node;
                }
     
                public boolean activeNodeHasEdgeStartingWith(final int value) {
                    return this.activeNode.getEdges().containsKey(value);
                }
     
                public boolean activeNodeHasSlink() {
                    return this.activeNode.getSlink() != null;
                }
     
                public boolean pointsToOnActiveEdge(final int[] values, final int value) {
                    return getActiveValue(values) == value;
                }
     
                public boolean pointsToTheEndOfActiveEdge() {
                    return this.getActiveEdge().getLength() == this.activeLength;
                }
     
                public boolean pointsAfterTheEndOfActiveEdge() {
                    return this.getActiveEdge().getLength() < this.activeLength;
                }
     
                public ActivePoint moveToEdgeStartingWithAndByOne(final int value) {
                    return new ActivePoint(this.activeNode, value, 1);
                }
     
                public ActivePoint moveToNextNodeOfActiveEdge() {
                    return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
                }
     
                public ActivePoint moveToSlink(final int[] values,
                                               final int suffixStartIndex,
                                               final int index) {
                    final int slinkIndex = suffixStartIndex + this.activeNode.getSlink().getValuesFromRootCount();
                    final int slinkValue = getSuffixValue(suffixStartIndex, values, slinkIndex);
                    final int slinkActiveLength = index - slinkIndex;
                    return new ActivePoint(this.activeNode.getSlink(),
                            slinkValue,
                            slinkActiveLength);
                }
     
                public ActivePoint moveTo(final Node node) {
                    return new ActivePoint(node, null, 0);
                }
     
                public ActivePoint moveTo(final Node node, final int activeLength) {
                    return new ActivePoint(node, 0, activeLength);
                }
     
                public ActivePoint moveByOneValue() {
                    return new ActivePoint(this.activeNode,
                            this.activeEdgeFirstValue,
                            this.activeLength + 1);
                }
     
                public ActivePoint moveToNextNodeOfActiveEdge(final int[] values,
                                                              final int suffixStartIndex) {
                    final int valueAtTheEndOfEdgeIndex = suffixStartIndex + this.activeNode.getValuesFromRootCount() + this.getActiveEdge()
                            .getLength();
                    final int valueAtTheEndOfEdge = getSuffixValue(suffixStartIndex, values, valueAtTheEndOfEdgeIndex);
                    return new ActivePoint(this.getActiveEdge().getNext(),
                            valueAtTheEndOfEdge,
                            this.activeLength - this.getActiveEdge().getLength());
                }
     
                public void addEdgeToActiveNode(final int value, final Edge edge) {
                    this.activeNode.getEdges().put(value, edge);
                }
     
                public Node splitActiveEdge(final int[] values,
                                            final int suffixStartIndex,
                                            final int index,
                                            final int value) {
                    final Node newNode = new Node(this.activeNode.getValuesFromRootCount()
                            + this.activeLength);
                    final Edge activeEdgeToSplit = this.getActiveEdge();
                    final Edge splittedEdge = new Edge(activeEdgeToSplit.getSuffixStartIndex(), activeEdgeToSplit.getFrom(),
                            activeEdgeToSplit.getFrom() + this.activeLength,
                            newNode);
                    newNode.getEdges().put(getActiveValue(values),
                            new Edge(activeEdgeToSplit.getSuffixStartIndex(),
                                    activeEdgeToSplit.getFrom() + this.activeLength,
                                    activeEdgeToSplit.getTo(),
                                    activeEdgeToSplit.getNext()));
                    newNode.getEdges().put(value, new Edge(suffixStartIndex, index, values.length, null));
                    this.activeNode.getEdges().put(this.activeEdgeFirstValue, splittedEdge);
                    return newNode;
                }
     
                public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                                       final Node node) {
                    if(previouslyAddedNodeOrAddedEdgeNode != null) {
                        previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
                    }
                    return node;
                }
     
                public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
                    return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
                }
            }
     
            private final int[] values;
            private final Node root;
            private ActivePoint activePoint;
            private int remainder;
            private long totalLeavesCount;
            private long leavesSum;
     
            public ST(final int[] values) {
                this.values = values;
                this.root = new Node(0);
                this.activePoint = new ActivePoint(this.root, null, 0);
                this.remainder = 0;
                this.totalLeavesCount = 0;
                this.leavesSum = 0;
                build();
            }
     
            private void build() {
                for(int i = 0; i < this.values.length; i++) {
                    add(i);
                }
            }
     
            private void add(final int index) {
                this.remainder++;
                boolean valueFoundInTheTree = false;
                Node previouslyAddedNodeOrAddedEdgeNode = null;
                while(!valueFoundInTheTree && this.remainder > 0) {
                    final int suffixStartIndex = index - this.remainder + 1;
                    final int valueToCheckExistanceInTree = this.activePoint.getSuffixValue(suffixStartIndex, this.values, index);
                    if(this.activePoint.pointsToActiveNode()) {
                        if(this.activePoint.activeNodeHasEdgeStartingWith(valueToCheckExistanceInTree)) {
                            activeNodeHasEdgeStartingWithValue(valueToCheckExistanceInTree,
                                    previouslyAddedNodeOrAddedEdgeNode);
                            valueFoundInTheTree = true;
                        }
                        else {
                            if(this.activePoint.activeNodeIs(this.root)) {
                                rootNodeHasNotEdgeStartingWithValue(suffixStartIndex, index, valueToCheckExistanceInTree);
                            }
                            else {
                                previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithValue(
                                        suffixStartIndex,
                                        index,
                                        valueToCheckExistanceInTree,
                                        previouslyAddedNodeOrAddedEdgeNode);
                            }
                        }
                    }
                    else {
                        if(this.activePoint.pointsToOnActiveEdge(this.values, valueToCheckExistanceInTree)) {
                            activeEdgeHasValue();
                            valueFoundInTheTree = true;
                        }
                        else {
                            if(this.activePoint.activeNodeIs(this.root)) {
                                previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotValue(suffixStartIndex,
                                        index,
                                        valueToCheckExistanceInTree,
                                        previouslyAddedNodeOrAddedEdgeNode);
                            }
                            else {
                                previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotValue(suffixStartIndex,
                                        index,
                                        valueToCheckExistanceInTree,
                                        previouslyAddedNodeOrAddedEdgeNode);
                            }
                        }
                    }
                }
                this.leavesSum += this.totalLeavesCount;
                System.out.println(this.leavesSum);
            }
     
            private void activeNodeHasEdgeStartingWithValue(final int value,
                                                            final Node previouslyAddedNodeOrAddedEdgeNode) {
                this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
                this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(value);
                if(this.activePoint.pointsToTheEndOfActiveEdge()) {
                    this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
                }
            }
     
            private void rootNodeHasNotEdgeStartingWithValue(final int suffixStartIndex, final int index, final int value) {
                this.activePoint.addEdgeToActiveNode(value, new Edge(suffixStartIndex, index, this.values.length, null));
                this.totalLeavesCount++;
                this.activePoint = this.activePoint.moveTo(this.root);
                this.remainder--;
                assert this.remainder == 0;
            }
     
            private Node internalNodeHasNotEdgeStartingWithValue(final int suffixStartIndex,
                                                                 final int index,
                                                                 final int value,
                                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
                this.activePoint.addEdgeToActiveNode(value, new Edge(suffixStartIndex, index, this.values.length, null));
                this.totalLeavesCount++;
                previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(
                        previouslyAddedNodeOrAddedEdgeNode);
                if(this.activePoint.activeNodeHasSlink()) {
                    this.activePoint = this.activePoint.moveToSlink(this.values, suffixStartIndex + 1, index);
                }
                else {
                    this.activePoint = this.activePoint.moveTo(this.root, this.remainder - 2);
                }
                this.activePoint = walkDown(suffixStartIndex + 1);
                this.remainder--;
                return previouslyAddedNodeOrAddedEdgeNode;
            }
     
            private void activeEdgeHasValue() {
                this.activePoint = this.activePoint.moveByOneValue();
                if(this.activePoint.pointsToTheEndOfActiveEdge()) {
                    this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
                }
            }
     
            private Node edgeFromRootNodeHasNotValue(final int suffixStartIndex,
                                                     final int index,
                                                     final int value,
                                                     Node previouslyAddedNodeOrAddedEdgeNode) {
                final Node newNode = this.activePoint.splitActiveEdge(this.values,
                        suffixStartIndex,
                        index,
                        value);
                this.totalLeavesCount++;
                previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode,
                        newNode);
                this.activePoint = this.activePoint.moveTo(this.root, this.remainder - 2);
                this.activePoint = walkDown(suffixStartIndex + 1);
                this.remainder--;
                return previouslyAddedNodeOrAddedEdgeNode;
            }
     
            private Node edgeFromInternalNodeHasNotValue(final int suffixStartIndex,
                                                         final int index,
                                                         final int value,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
                final Node newNode = this.activePoint.splitActiveEdge(this.values,
                        suffixStartIndex,
                        index,
                        value);
                this.totalLeavesCount++;
                previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode,
                        newNode);
                if(this.activePoint.activeNodeHasSlink()) {
                    this.activePoint = this.activePoint.moveToSlink(this.values, suffixStartIndex + 1, index);
                }
                else {
                    this.activePoint = this.activePoint.moveTo(this.root, this.remainder - 2);
                }
                this.activePoint = walkDown(suffixStartIndex + 1);
                this.remainder--;
                return previouslyAddedNodeOrAddedEdgeNode;
            }
     
            private ActivePoint walkDown(final int suffixStartIndex) {
                while(!this.activePoint.pointsToActiveNode()
                        && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
                    if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
                        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.values, suffixStartIndex);
                    }
                    else {
                        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
                    }
                }
                return this.activePoint;
            }
        }
     
        public static void main(final String[] args) {
            final Scanner in = new Scanner(System.in);
            final String line = in.next();
            final char[] charsLine = line.toCharArray();
            final int[] indexesMinusprevOccurenceIndexes = new int[line.length()];
            final Map<Character, Integer> prev = new HashMap<>();
            for(int i = 0; i < line.length(); i++) {
                if(prev.containsKey(charsLine[i])) {
                    indexesMinusprevOccurenceIndexes[i] = i - prev.get(charsLine[i]);
                }
                prev.put(charsLine[i], i);
            }
            new ST(indexesMinusprevOccurenceIndexes);
        }
    }
    
    2|
    Permalink
  • goodday04041
    1 year ago+ 0 comments

    The worst explaination!

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature