#include <stdio.h>
/*感觉稍微难点的三个：
1）设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)


3）设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，则中国人民 人民中国都有效。要求：
  1）系统每秒的查询数量可能上千次；
  2）词语的数量级为10W；
  3）每个词至多可以与1W个词搭配
 
 当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息.
 */

/*2）一串首尾相连的珠子（m个），有N种颜色（N《=10），设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。
time: O(m)
space: O(N)*/
#define MAX_N 10
bool Select(int m, int const *data, int n, int *start_idx, int *length)
{
    int color[MAX_N];
    int nColor=0;
    memset(color, 0, sizeof(color));

    *start_idx = 0, *length = m;
    
    int best_start_idx = 0;
    int best_length = m;

    for(int i=0; i<m-n; i++)
    {
        if(!color[data[i]]) nColor++;
        color[data[i]]++;

        if(nColor==n && i-best_start_idx+1<best_length)
        {
            best_length = i-best_start_idx+1;
            *start_idx = best_start_idx;

            color[data[best_start_idx]]--;
            if(0==color[data[i]])
                nColor--;
            else
                i--;
            best_start_idx++;
        }
    }

    return true;
}

int main(int argc, char *argv[])
{
    int n=6;
    int data[]={0,1,2,3,4,4,5,4,2,3,1,0,2,3};
    int m = sizeof(data)/sizeof(data[0]);

    int start_idx;
    int length;
    Select(m, data, n, &start_idx, &length);

    return 0;
}