Stacks Binary Trees

Find the lexicographically smallest substring with distinct characters

Stacks
JavaScript

Problem:

Given a string, find the lexicographically smallest subsequence that can be formed using all distinct characters only once from the given string. The input string will only contain lowercase English letters.

Example:

Input string: ‘bcabc’

Output: ‘abc’

Input string: ‘cbacdcbc’

Output: ‘acdb’

Algorithm:

To solve this, we will start from the given index of the opening bracket and push brackets onto the stack. When we encounter a closing bracket, we pop the opening bracket from the stack. If the stack becomes empty after popping, the current index will be the index of the closing bracket.

Steps:

  1. Loop through the characters of the string in reverse order to construct the smallest subsequence.
  2. If duplicate characters are encountered, compare the current character with the first character of the subsequence.
    1. If the current character is larger than the first character of the subsequence, ignore it.
    2. If the current character is smaller or equal, prepend it to the subsequence and remove the duplicate character already present in the subsequence.
  3. After completing these steps, the resulting subsequence will be the smallest possible subsequence.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm to reverse a string works. Feel free to experiment by changing the input strings.

Result
Code

Input:

The string should only contain the lowercase English letters.

Output:

   
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
    let string = args[0];
    let smallestString = '';

    const stack = new Stack(
        string.split(''),
        {
            name: 'Stack',
            description: 'This stack will hold the characters of the given string.'
        }
    );

    let topChar = '';
    let charCount = {};
    let i = string.length - 1;
    while (! stack.isEmpty()) {
        animatorModule.displayComment(
            'Pop each element from the stack and compare it with first letter of string. <br>'
            + highlightCharacter(string, i)
            + '<br> Current smallest subsequence: <div class="sv-comment-highlight">'
            + highlightCharacter(smallestString, 0) +'</div>',
            200
        );

        topChar = stack.pop();

        // Increment the count or set the count to 1
        charCount[topChar] = (charCount[topChar] || 0) + 1;

        if (smallestString.length > 0 && charCount[topChar] > 1) {
            if (topChar > smallestString[0]) {
                animatorModule.displayComment(
                    'Popped element ('+ topChar +') > first letter ('+ smallestString[0] +'). So ignore it. <br>'
                    + highlightCharacter(string, i)
                    + ' <br> Current smallest subsequence: <div class="sv-comment-highlight">'
                    + highlightCharacter(smallestString, 0) +'</div>',
                    2000
                );
            } else {
                smallestString = smallestString.replace(topChar, '');
                smallestString = topChar + smallestString;

                animatorModule.displayComment(
                    'Popped element ('+ topChar +') <= first letter ('+ smallestString[0] +'). So ignore the duplicate character already present in the string. <br>'
                    + highlightCharacter(string, i)
                    + ' <br> Current smallest subsequence: <div class="sv-comment-highlight">'
                    + highlightCharacter(smallestString, 0) +'</div>',
                    2000
                );
            }

        } else {
            if (smallestString.length > 0) {
                animatorModule.displayComment(
                    'Pop each element from the stack and compare it with first letter of string. <br>'
                    + highlightCharacter(string, i)
                    + ' <br> Current smallest subsequence: <div class="sv-comment-highlight">'
                    + highlightCharacter(smallestString, 0) +'</div>',
                    200
                );
            }

            smallestString = topChar + smallestString;
        }

        i--;
    }

    animatorModule.displayOutput(smallestString);
    animatorModule.displayComment(
        'Lexicographically smallest subsequence: <br>'
        + highlightSubstring(smallestString, 0, smallestString.length)
    );
    return smallestString;
}
                                        
class Stack {
    metaData = {
        'name': 'Stack',
        'description': '',
        'animation_duration': 1500,
    }

    constructor(initialData, metaData) {
        this.initialData = [...initialData];
        this.metaData = Object.assign({}, this.metaData, metaData);

        this.stackDisplayer = new StackDisplayer(initialData, this.metaData);
        this.stackId = this.stackDisplayer.display();
    }

    getStackData() {
        return this.initialData;
    }

    push(value) {
        this.initialData.push(value);

        // Perform the animation
        animatorModule.performPushAnimation(this.stackId, value);
    }

    pop() {
        if (this.initialData.length == 0) return;

        const value = this.initialData.pop();

        // Perform the animation
        animatorModule.performPopAnimation(this.stackId, value);

        return value;
    }

    top() {
        if (this.initialData.length == 0) return;

        const value = this.initialData[this.initialData.length - 1];

        return value;
    }

    isEmpty() {
        return this.initialData.length === 0;
    }
}
                                        
class StackDisplayer {
    constructor(initialData, metaData) {
        this.initialData = initialData;
        this.metaData = metaData;
    }

    display() {
        // Display stack on the screen
        const stackTemplate = document.getElementById('stack-template');
        const clone = stackTemplate.content.cloneNode(true);
        const stackCount = document.getElementsByClassName('stack-wrapper').length + 1;

        // Add an unique ID to the clone
        const stackWrapperId = 'stack-' + stackCount;
        const stackWrapper = clone.querySelector('.stack-wrapper');
        stackWrapper.id = stackWrapperId;

        // Add initial stack items
        const stackElement = clone.querySelector('.stack');
        while(this.initialData.length) {
            stackElement.insertAdjacentHTML(
                'beforeend',
                '<div class="stack-item">'+ this.initialData.pop() +'</div>'
            )
        }

        clone.querySelector('.stack-description h4')
             .textContent = this.metaData.name;
        clone.querySelector('.stack-description p')
             .textContent = this.metaData.description;

        document.getElementById('stack-visualizer')
                .appendChild(clone);

        return stackWrapperId;
    }
}
                                        
class AnimationList {
    animations = [];

    length() {
        return this.animations.length;
    }

    push(animation) {
        this.animations.push(animation);
    }

    shift() {
        return this.animations.shift();
    }
}

let animatorModule = (function() {
    let animations = new AnimationList();
    let animationsRunning = false;
    let animationSpeed = 1200;

    function getMoveDownAnimation(animation) {
        let topElement = animation.stackElement.children[0];

        let distance = animation.stackElement.offsetHeight;
        if (topElement) {
            distance = topElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().height
                        - 2; // Margin bottom
        }

        let moveDownAnimation = [
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            '0',
            (0.2 * distance) +  'px',
            (0.37 * distance) +  'px',
            (0.55 * distance) +  'px',
            (0.7 * distance) +  'px',
            (0.87 * distance) +  'px',
            distance  + 'px',
            distance  + 'px'
        ];

        return moveDownAnimation;
    }

    function getMoveUpAnimation(animation) {
        let topElement = animation.stackElement.children[0];
        let distance = topElement.getBoundingClientRect().y
                        - animation.pushElement.getBoundingClientRect().y;

        let moveUpAnimation = [
            (distance - 0.95 * distance) +  'px',
            (distance - 0.87 * distance) +  'px',
            (distance - 0.7 * distance) +  'px',
            (distance - 0.55 * distance) +  'px',
            (distance - 0.37 * distance) +  'px',
            (distance - 0.2 * distance) +  'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px',
            distance + 'px'
        ];

        return moveUpAnimation;
    }

    function pushAnimate(animation) {
        animation.pushElement.textContent = animation.value;

        let pushAnimationKeyFrames = {
            // 25% - Show element
            opacity: ['0', '0.3', '0.7', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'],
            left: ['0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px'],
            top: getMoveDownAnimation(animation),
            offset: [0, 0.08, 0.16, 0.25, 0.25, 0.31, 0.37, 0.43, 0.5, 0.56, 0.62, 0.68, 0.73, 0.78, 0.83, 0.88, 0.93, 0.98, 1]
        };

        let duplicateElement = animation.pushElement.cloneNode(true);
        duplicateElement.classList.remove('hidden');

        // TODO: Increase the height of the stack before pushing

        let pushAnimation = animation.pushElement.animate(pushAnimationKeyFrames, animationSpeed);

        return new Promise((resolve) => {
            return pushAnimation.finished.then(() => {
                animation.stackElement.prepend(duplicateElement);
                resolve(`Push Animation completed!`);
            });
        })
    }

    function popAnimate(animation) {
        let popAnimationKeyFrames = {
            bottom: getMoveUpAnimation(animation),
            left: ['0', '0', '0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px'],
            offset: [0, 0.07, 0.15, 0.22, 0.3, 0.37, 0.45, 0.52, 0.6, 0.67, 0.75, 0.82, 0.9, 1]
        };

        let topElement = animation.stackElement.children[0];

        let popAnimation = topElement.animate(popAnimationKeyFrames, animationSpeed);
        // The animation is not smooth
        // So remove the item before animation is completed
        setTimeout(() => {
            topElement.remove();
            animation.popElement.textContent = topElement.textContent;
        }, animationSpeed - 200);

        return new Promise((resolve) => {
            return popAnimation.finished.then(() => {
                // topElement.remove();
                // animation.popElement.textContent = topElement.textContent;
                resolve(`Pop Animation completed!`);
            });
        })
    }

    function displayCommentAnimate(animation) {
        return new Promise((resolve) => {
            document.getElementsByClassName('sv-comment')[0]
                    .innerHTML = animation.value;

            setTimeout(() => {
                resolve('Comment displayed!');
            }, animation.timeout);
        })
    }

    function displayOutputAnimate(animation) {
        return new Promise((resolve) => {
            let outputELement = document.getElementById('final-output');
            outputELement.innerHTML = animation.value;
            resolve('Output displayed!');
        })
    }

    function runSingleAnimation(animation) {
        switch (animation.type) {
            case 'push':
                return pushAnimate(animation);
                break;
            case 'pop':
                return popAnimate(animation);
                break;
            case 'display-comment':
                return displayCommentAnimate(animation);
                break;
            case 'display-output':
                return displayOutputAnimate(animation);
                break;
        }
    }

    function runAnimations() {
        if (animationsRunning) return;

        animationsRunning = true;
        // Perform the animations one after the other
        let animation = animations.shift();
        runSingleAnimation(animation)
            .then(() => {
                animationsRunning = false;
                if (animations.length()) {
                    runAnimations();
                }
            });
    }

    function getStackElements(stackId) {
        let stackWrapper = document.getElementById(stackId);
        return {
            stackElement: stackWrapper.getElementsByClassName('stack')[0],
            pushElement: stackWrapper.getElementsByClassName('push-element')[0],
            popElement: stackWrapper.getElementsByClassName('pop-element')[0]
        }
    }

    let performPushAnimation = function (stackId, value) {
        let animationObject = Object.assign(
                                {type: 'push', value: value},
                                getStackElements(stackId)
                            );
        animations.push(animationObject);

        runAnimations();
    }

    let performPopAnimation = function (stackId, value) {
        let animationObject = Object.assign(
                                {type: 'pop', value: value},
                                getStackElements(stackId)
                            );
        animations.push(animationObject);

        runAnimations();
    }

    /**
     * Set the animation duration.
     *
     * @param flot speed Duration in seconds (1, 2.5...)
     */
    let setAnimationSpeed = function (speed) {
        animationSpeed = speed * 1000;
    }

    let displayComment = function (comment, timeout = 0) {
        let animationObject = {
            type: 'display-comment',
            value: comment,
            timeout: timeout
        };

        animations.push(animationObject);
        runAnimations();
    }

    let displayOutput = function (output) {
        let animationObject = {
            type: 'display-output',
            value: output
        };

        animations.push(animationObject);
        runAnimations();
    }

    let clearAnimations = function () {
        animations = new AnimationList();
        animationsRunning = false;
    }

    return {
        performPushAnimation: performPushAnimation,
        performPopAnimation: performPopAnimation,
        setAnimationSpeed: setAnimationSpeed,
        displayComment: displayComment,
        displayOutput: displayOutput,
        clearAnimations: clearAnimations
    }
})();